Boundaries and Hulls of Euclidean Graphs: From Theory to Practice

Description

Boundaries and Hulls of Euclidean Graphs: From Theory to Practice presents concepts and algorithms for finding convex, concave and polygon hulls of Euclidean graphs. It also includes some implementations, determining and comparing their complexities. Since the implementation is application-dependent, either centralized or distributed, some basic concepts of the centralized and distributed versions are reviewed. Theoreticians will find a presentation of different algorithms together with an evaluation of their complexity and their utilities, as well as their field of application. Practitioners will find some practical and real-world situations in which the presented algorithms can be used. Cover Half Title Title Page Copyright Page Dedication Table of Contents Acknowledgments Preface 1: Fundamentals on graphs and computational geometry 1.1 Basic definitions 1.2 Partial graphs and subgraphs 1.3 Chains and cycles 1.4 Some classes of graphs 1.5 Hamiltonian graphs 1.6 Planar graphs 1.7 Trees 1.7.1 Properties 1.7.2 Spanning trees 1.7.3 Minimum spanning trees 1.8 Non-graphical representations of a graph 1.8.1 Adjacency matrices 1.8.2 Adjacency lists 1.9 Computational geometry 1.9.1 Triangulations 1.9.2 Delaunay triangulations 1.9.3 Planar straight-line graphs 1.9.4 Euclidean graphs 1.10 Polygons and pseudo-polygons 1.10.1 Polygons 1.10.2 Pseudo-polygons 1.11 Angles and visits 1.11.1 Visiting vertices 1.11.2 Visiting polar angles 1.11.3 Interior and exterior angles and polygons 1.11.3.1 Angle-based method 1.11.3.2 Minimum x-coordinate based method 2: Hulls of point sets and graphs 2.1 Convex hull 2.1.1 Definitions and properties 2.1.2 Examples 2.2 Affine hull 2.2.1 Definitions and properties 2.2.2 Examples 2.3 α-shape 2.3.1 Definition and properties 2.3.2 α-complex 2.3.3 Relation between α-shape and Delaunay triangulation 2.3.4 Examples 2.4 Boundaries of graphs 2.4.1 Polygon hull of plane Euclidean graphs 2.4.2 Properties 2.4.3 Polygon hull of general Euclidean graphs 2.4.3.1 A-polygon hull 2.4.3.2 B-polygon hull 2.4.3.3 C-polygon hull 3: Centralized algorithms for boundary detection 3.1 Finding the convex hull of a set of points in the plane 3.1.1 Jarvis' algorithm 3.1.2 Graham's algorithm 3.1.3 The Quickhull algorithm 3.1.4 Andrew's algorithm 3.1.5 Kallay's algorithm 3.1.6 Chan's algorithm 3.2 Finding a concave hull of a set of points in the plane 3.2.1 Split and merge 3.2.2 Perceptual boundary extraction 3.2.3 K-nearest neighbor 3.2.4 Concaveness measure 3.3 Finding a polygon hull of a Euclidean graph 3.3.1 LPCN: Least Polar-angle Connected Node algorithm to find a polygon hull of a connected Euclidean graph 3.3.2 Concave hull of a plane Euclidean graph 3.3.3 Concave hull of a general Euclidean graph 3.3.3.1 A-polygon hull 3.3.3.2 B-polygon hull 3.3.3.3 C-polygon hull 3.4 Finding the polygon hull of a Euclidean graph without conditions on the starting vertex 4: Distributed algorithms for boundary detection 4.1 What is a distributed algorithm? 4.2 Basic concepts 4.3 Complexity of distributed algorithms 4.4 Functions and message primitives 4.5 Trees and transmissions 4.5.1 Flooding and spanning tree 4.5.2 Flooding for Leaf Finding 4.6 Leader election 4.6.1 Wait-Before-Starting 4.6.2 Minimum Finding 4.6.2.1 Local Minima Finding 4.6.2.2 Global Minimum Finding 4.6.3 Local Minima to Global Minimum (LOGO) 4.6.3.1 The concept 4.6.3.2 The algorithm 4.6.4 Branch Optima to Global Optimum (BrOGO) 4.6.4.1 The concept 4.6.4.2 The algorithm 4.6.5 Dominating Tree Routing (DoTRo) 4.6.5.1 The concept 4.6.5.2 The algorithm 4.6.6 Comparison of the leader election algorithms 4.7 Polygon hull 4.7.1 The D-LPCN algorithm 4.7.2 The D-RRLPCN algorithm 5: The simulator CupCarbon and boundary detection 5.1 CupCarbon for network simulation 5.2 The environment of CupCarbon 5.2.1 Menu bar 5.2.2 Map 5.2.3 Toolbar 5.2.4 Parameter menu 5.2.5 Console 5.3 The objects of CupCarbon 5.3.1 Sensor node 5.3.2 Base station (Sink) 5.3.3 Analog events (Gas) 5.3.4 Mobile 5.3.5 Marker 5.4 An introduction to SenScript 5.5 SenScript examples 5.5.1 Sending and receiving messages 5.5.2 Routing 5.5.3 Flooding 5.5.4 Flooding for Leaf Finding (FLF) 5.5.5 Wait-Before-Starting (WBS) 5.5.6 Wait-Before-Starting with Flooding 5.5.7 Wait-Before-Starting with FLF 5.5.8 Local Minima Finding 5.5.9 Global Minimum Finding 5.5.10 The R-LOGO algorithm 5.5.11 The R-BrOGO algorithm 5.5.12 The DoTRo algorithm 5.6 SenScript of the D-LPCN algorithm 5.6.1 Version 1: fixing the starting node manually 5.6.2 Version 2: starting from Minimum Finding 5.6.3 Version 3: starting from R-BrOGO 5.6.4 Version 4: starting from DoTRo 6: Applications 6.1 Finding the boundary nodes of a WSN 6.2 Boundary node failure detection and reconfiguration 6.3 Finding voids and gaps in WSNs 6.4 Cluster finding and shape reconstruction 6.5 Image contour polygon 6.6 Polygon hull in an angle graph Bibliography Index