Boundaries and Hulls of Euclidean Graphs

Cover......Page 1
Half Title......Page 2
Title Page......Page 4
Copyright Page......Page 5
Dedication......Page 6
Table of Contents......Page 8
Acknowledgments......Page 12
Preface......Page 14
1.1 Basic definitions......Page 18
1.2 Partial graphs and subgraphs......Page 19
1.3 Chains and cycles......Page 20
1.4 Some classes of graphs......Page 21
1.5 Hamiltonian graphs......Page 23
1.6 Planar graphs......Page 24
1.7.3 Minimum spanning trees......Page 25
1.8 Non-graphical representations of a graph......Page 26
1.9 Computational geometry......Page 27
1.9.2 Delaunay triangulations......Page 28
1.9.3 Planar straight-line graphs......Page 29
1.9.4 Euclidean graphs......Page 30
1.10.1 Polygons......Page 31
1.10.2 Pseudo-polygons......Page 33
1.11 Angles and visits......Page 35
1.11.2 Visiting polar angles......Page 37
1.11.3 Interior and exterior angles and polygons......Page 38
1.11.3.1 Angle-based method......Page 40
1.11.3.2 Minimum x-coordinate based method......Page 44
2.1.1 Definitions and properties......Page 50
2.1.2 Examples......Page 52
2.2.1 Definitions and properties......Page 53
2.2.2 Examples......Page 54
2.3.1 Definition and properties......Page 55
2.3.3 Relation between α-shape and Delaunay triangulation......Page 57
2.4 Boundaries of graphs......Page 58
2.4.3 Polygon hull of general Euclidean graphs......Page 59
2.4.3.2 B-polygon hull......Page 61
2.4.3.3 C-polygon hull......Page 62
3.1 Finding the convex hull of a set of points in the plane......Page 64
3.1.1 Jarvis' algorithm......Page 65
3.1.3 The Quickhull algorithm......Page 67
3.1.4 Andrew's algorithm......Page 69
3.1.5 Kallay's algorithm......Page 72
3.1.6 Chan's algorithm......Page 73
3.2 Finding a concave hull of a set of points in the plane......Page 74
3.2.1 Split and merge......Page 75
3.2.2 Perceptual boundary extraction......Page 76
3.2.3 K-nearest neighbor......Page 77
3.2.4 Concaveness measure......Page 78
3.3.1 LPCN: Least Polar-angle Connected Node algorithm to find a polygon hull of a connected Euclidean graph......Page 79
3.3.3.1 A-polygon hull......Page 80
3.3.3.2 B-polygon hull......Page 82
3.3.3.3 C-polygon hull......Page 85
3.4 Finding the polygon hull of a Euclidean graph without conditions on the starting vertex......Page 88
4.1 What is a distributed algorithm?......Page 94
4.2 Basic concepts......Page 97
4.3 Complexity of distributed algorithms......Page 99
4.5.1 Flooding and spanning tree......Page 101
4.5.2 Flooding for Leaf Finding......Page 102
4.6.1 Wait-Before-Starting......Page 104
4.6.2 Minimum Finding......Page 105
4.6.2.1 Local Minima Finding......Page 106
4.6.2.2 Global Minimum Finding......Page 107
4.6.3.1 The concept......Page 108
4.6.3.2 The algorithm......Page 109
4.6.4.1 The concept......Page 113
4.6.4.2 The algorithm......Page 115
4.6.5.2 The algorithm......Page 120
4.6.6 Comparison of the leader election algorithms......Page 123
4.7.1 The D-LPCN algorithm......Page 131
4.7.2 The D-RRLPCN algorithm......Page 132
5: The simulator CupCarbon and boundary detection......Page 138
5.1 CupCarbon for network simulation......Page 139
5.2.1 Menu bar......Page 140
5.2.4 Parameter menu......Page 142
5.3.1 Sensor node......Page 144
5.3.3 Analog events (Gas)......Page 145
5.3.5 Marker......Page 146
5.4 An introduction to SenScript......Page 148
5.5.1 Sending and receiving messages......Page 150
5.5.2 Routing......Page 151
5.5.3 Flooding......Page 152
5.5.5 Wait-Before-Starting (WBS)......Page 153
5.5.6 Wait-Before-Starting with Flooding......Page 154
5.5.7 Wait-Before-Starting with FLF......Page 155
5.5.9 Global Minimum Finding......Page 156
5.5.10 The R-LOGO algorithm......Page 157
5.5.11 The R-BrOGO algorithm......Page 159
5.5.12 The DoTRo algorithm......Page 162
5.6.1 Version 1: fixing the starting node manually......Page 164
5.6.2 Version 2: starting from Minimum Finding......Page 166
5.6.3 Version 3: starting from R-BrOGO......Page 167
5.6.4 Version 4: starting from DoTRo......Page 170
6.1 Finding the boundary nodes of a WSN......Page 174
6.2 Boundary node failure detection and reconfiguration......Page 177
6.3 Finding voids and gaps in WSNs......Page 180
6.4 Cluster finding and shape reconstruction......Page 183
6.5 Image contour polygon......Page 189
6.6 Polygon hull in an angle graph......Page 197
Bibliography......Page 204
Index......Page 216