Muutke küpsiste eelistusi

Boundaries and Hulls of Euclidean Graphs: From Theory to Practice [Kõva köide]

5.00/5 (2 hinnangut Goodreads-ist)
, ,
  • Formaat: Hardback, 218 pages, kõrgus x laius: 234x156 mm, kaal: 456 g, 5 Tables, black and white; 127 Illustrations, black and white
  • Ilmumisaeg: 26-Jul-2018
  • Kirjastus: CRC Press
  • ISBN-10: 1138048917
  • ISBN-13: 9781138048911
Teised raamatud teemal:
Boundaries and Hulls of Euclidean Graphs: From Theory to PracticeSuurem pilt
  • Formaat: Hardback, 218 pages, kõrgus x laius: 234x156 mm, kaal: 456 g, 5 Tables, black and white; 127 Illustrations, black and white
  • Ilmumisaeg: 26-Jul-2018
  • Kirjastus: CRC Press
  • ISBN-10: 1138048917
  • ISBN-13: 9781138048911
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9781138048911.html
Märksõnad:

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.

Arvustused

This book is intended for readers working on problems that can be represented as a network or generally as a connected Euclidean graph. It gives the necessary basic mathematical tools and the most recent algorithms to find boundary nodes and polygon hulls in this types of graphs. The authors present the graph theory in a rigorous, but informal style and cover most of the relevant areas.

Since the presented algorithms can also be used for distributed or autonomous communicating systems like computers, cars, UAVs, people or smartphones, etc., the books offers an introduction into distributed programming, followed by the distributed versions of all those algorithms presented in their centralized form. Finally, the reader is also offered a platform called CupCarbon which is a simulator of WSNs dedicated to Smart-cities and IoT. This platform, available online as an open source software, offers an ergonomic and easy to use interface for visualization allowing to develop and validate algorithms, to check and understand visually what happens during simulation.

The book is highly accessible and engaging. It summarizes the main research of the authors during the last 3 years at the crossroad of Graph and Network theory, Computational Geometry, Communication and Simulation. The results have been presented at high-level, international conferences and published in recognized journals of these fields. The text is suitable for students in computer science or mathematics programs and it can be used for research as well as high-level university education.

-Professor Pietro Manzoni, Universitat Politècnica de Valéncia

The book presents a series of algorithms for the determination of the boundary nodes and the polygonal envelope of a Euclidean graph. There is not much work in the literature dealing with this problem in an algorithmic way. Most of the existing work is directly related to practical cases such as sensor netw

Acknowledgments xi
Preface xiii
1 Fundamentals on graphs and computational geometry
1(32)
1.1 Basic definitions
1(1)
1.2 Partial graphs and subgraphs
2(1)
1.3 Chains and cycles
3(1)
1.4 Some classes of graphs
4(2)
1.5 Hamiltonian graphs
6(1)
1.6 Planar graphs
7(1)
1.7 Trees
8(1)
1.7.1 Properties
8(1)
1.7.2 Spanning trees
8(1)
1.7.3 Minimum spanning trees
8(1)
1.8 Non-graphical representations of a graph
9(1)
1.8.1 Adjacency matrices
10(1)
1.8.2 Adjacency lists
10(1)
1.9 Computational geometry
10(4)
1.9.1 Triangulations
11(1)
1.9.2 Delaunay triangulations
11(1)
1.9.3 Planar straight-line graphs
12(1)
1.9.4 Euclidean graphs
13(1)
1.10 Polygons and pseudo-polygons
14(4)
1.10.1 Polygons
14(2)
1.10.2 Pseudo-polygons
16(2)
1.11 Angles and visits
18(15)
1.11.1 Visiting vertices
20(1)
1.11.2 Visiting polar angles
20(1)
1.11.3 Interior and exterior angles and polygons
21(2)
1.11.3.1 Angle-based method
23(4)
1.11.3.2 Minimum x-coordinate based method
27(6)
2 Hulls of point sets and graphs
33(14)
2.1 Convex hull
33(3)
2.1.1 Definitions and properties
33(2)
2.1.2 Examples
35(1)
2.2 Affinehull
36(2)
2.2.1 Definitions and properties
36(1)
2.2.2 Examples
37(1)
2.3 α-shape
38(3)
2.3.1 Definition and properties
38(2)
2.3.2 α-complex
40(1)
2.3.3 Relation between α-shape and Delaunay triangulation
40(1)
2.3.4 Examples
41(1)
2.4 Boundaries of graphs
41(6)
2.4.1 Polygon hull of plane Euclidean graphs
42(1)
2.4.2 Properties
42(1)
2.4.3 Polygon hull of general Euclidean graphs
42(2)
2.4.3.1 A-polygon hull
44(1)
2.4.3.2 B-polygon hull
44(1)
2.4.3.3 C-polygon hull
45(2)
3 Centralized algorithms for boundary detection
47(30)
3.1 Finding the convex hull of a set of points in the plane
47(10)
3.1.1 Jarvis' algorithm
48(2)
3.1.2 Graham's algorithm
50(1)
3.1.3 The Quickhull algorithm
50(2)
3.1.4 Andrew's algorithm
52(3)
3.1.5 Kallay's algorithm
55(1)
3.1.6 Chan's algorithm
56(1)
3.2 Finding a concave hull of a set of points in the plane
57(5)
3.2.1 Split and merge
58(1)
3.2.2 Perceptual boundary extraction
59(1)
3.2.3 K-nearest neighbor
60(1)
3.2.4 Concaveness measure
61(1)
3.3 Finding a polygon hull of a Euclidean graph
62(9)
3.3.1 LPCN: Least Polar-angle Connected Node algorithm to find a polygon hull of a connected Euclidean graph
62(1)
3.3.2 Concave hull of a plane Euclidean graph
63(1)
3.3.3 Concave hull of a general Euclidean graph
63(1)
3.3.3.1 A-polygon hull
63(2)
3.3.3.2 B-polygon hull
65(3)
3.3.3.3 C-polygon hull
68(3)
3.4 Finding the polygon hull of a Euclidean graph without conditions on the starting vertex
71(6)
4 Distributed algorithms for boundary detection
77(44)
4.1 What is a distributed algorithm?
77(3)
4.2 Basic concepts
80(2)
4.3 Complexity of distributed algorithms
82(2)
4.4 Functions and message primitives
84(1)
4.5 Trees and transmissions
84(3)
4.5.1 Flooding and spanning tree
84(1)
4.5.2 Flooding for Leaf Finding
85(2)
4.6 Leader election
87(27)
4.6.1 Wait-Before-Starting
87(1)
4.6.2 Minimum Finding
88(1)
4.6.2.1 Local Minima Finding
89(1)
4.6.2.2 Global Minimum Finding
90(1)
4.6.3 Local Minima to Global Minimum (LOGO)
91(1)
4.6.3.1 The concept
91(1)
4.6.3.2 The algorithm
92(4)
4.6.4 Branch Optima to Global Optimum (BrOGO)
96(1)
4.6.4.1 The concept
96(2)
4.6.4.2 The algorithm
98(5)
4.6.5 Dominating Tree Routing (DoTRo)
103(1)
4.6.5.1 The concept
103(1)
4.6.5.2 The algorithm
103(3)
4.6.6 Comparison of the leader election algorithms
106(8)
4.7 Polygon hull
114(7)
4.7.1 The D-LPCN algorithm
114(1)
4.7.2 The D-RRLPCN algorithm
115(6)
5 The simulator CupCarbon and boundary detection
121(36)
5.1 CupCarbon for network simulation
122(1)
5.2 The environment of CupCarbon
123(4)
5.2.1 Menu bar
123(2)
5.2.2 Map
125(1)
5.2.3 Toolbar
125(1)
5.2.4 Parameter menu
125(2)
5.2.5 Console
127(1)
5.3 The objects of CupCarbon
127(4)
5.3.1 Sensor node
127(1)
5.3.2 Base station (Sink)
128(1)
5.3.3 Analog events (Gas)
128(1)
5.3.4 Mobile
129(1)
5.3.5 Marker
129(2)
5.4 An introduction to SenScript
131(2)
5.5 SenScript examples
133(14)
5.5.1 Sending and receiving messages
133(1)
5.5.2 Routing
134(1)
5.5.3 Flooding
135(1)
5.5.4 Flooding for Leaf Finding (FLF)
136(1)
5.5.5 Wait-Before-Starting (WBS)
136(1)
5.5.6 Wait-Before-Starting with Flooding
137(1)
5.5.7 Wait-Before-Starting with FLF
138(1)
5.5.8 Local Minima Finding
139(1)
5.5.9 Global Minimum Finding
139(1)
5.5.10 The R-LOGO algorithm
140(2)
5.5.11 The R-BrOGO algorithm
142(3)
5.5.12 The DoTRo algorithm
145(2)
5.6 SenScript of the D-LPCN algorithm
147(10)
5.6.1 Version 1: fixing the starting node manually
147(2)
5.6.2 Version 2: starting from Minimum Finding
149(1)
5.6.3 Version 3: starting from R-BrOGO
150(3)
5.6.4 Version 4: starting from DoTRo
153(4)
6 Applications
157(30)
6.1 Finding the boundary nodes of a WSN
157(3)
6.2 Boundary node failure detection and reconfiguration
160(3)
6.3 Finding voids and gaps in WSNs
163(3)
6.4 Cluster finding and shape reconstruction
166(6)
6.5 Image contour polygon
172(8)
6.6 Polygon hull in an angle graph
180(7)
Bibliography 187(12)
Index 199
Ahcène Bounceur is an associate professor of computer science at Lab-STICC laboratory (CNRS 6285), University of Brest, France. His current research activities are focused on: tools for parallel and physical simulation of WSNs dedicated to Smart-cities and IoT, distributed algorithms and sampling methods for Big Data mining.

Madani Bezoui is an assistant professor of operations research at the University of Boumerdes, Algeria. His research interests include: combinatorial algorithms and optimization, multi-objective optimization, portfolio selection, Big Data and IoT.

Reinhardt Euler is a professor of computer science at Lab-STICC laboratory (CNRS 6285), University of Brest, France. His research interests include: combinatorial algorithms and optimization, graph theory, and the efficient solution of large-scale, real-life problem instances.