1st Edition

Boundaries and Hulls of Euclidean Graphs From Theory to Practice

    217 Pages
    by Chapman & Hall

    218 Pages 127 B/W Illustrations
    by Chapman & Hall

    217 Pages 127 B/W Illustrations
    by Chapman & Hall

    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.

    1 Fundamentals on graphs and computational geometry. 2 Hulls of point sets and graphs. 3 Centralized algorithms. 4 Distributed algorithms. 5 The Simulator CupCarbon and Boundary Detection. 6 Applications


    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.

    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