Boundaries and Hulls of Euclidean Graphs

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.

• 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

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énciaThe 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 networks in which the proposed methods are often heuristics. This book proposes algorithms based on geometry where the polygonal envelope is determined using angles formed by adjacent edges of a graph. The key algorithm of this book is the LPCN algorithm which represents a promising and interesting contribution. This algorithm is also presented in its distributed form under the name of D-LPCN, a form that allows to be implemented in real networks such as wireless sensor networks or distributed systems in general.The book contains 6 chapters. The first chapter introduces basic notions on graphs and computational geometry. This chapter is essential for understanding the concepts presented in the other chapters. It also introduces the new concept of pseudo-polygons which represent geometric shapes close to polygons with the same characteristics or which could be transformed into polygons. It also introduces the notions of visits and polar angles which allows to look at polygons differently and to better understand the working principle of the algorithms.The concepts of convex and polygonal hulls are presented in Chapter 2. The novelty of this chapter lies in the presentation of the different forms of the polygonal hull as well as their mathematical models. This is relevant since, unlike the convex hull, the polygonal hull can have several possible forms.Chapters 3 and 4 present the algorithms to determine the convex and polygonal hulls of Euclidean graphs. These algorithms are presented in their centralized and distributed form. In addition, Chapter 4 presents new algorithms for the problem of leader election in distributed systems which guarantee a very significant reduction of the amount of communication messages exchanged between the nodes of the system in question. These algorithms are used to determine the starting node of distributed algorithms. This chapter also presents a very interesting introduction to distributed programming and its difference with centralized and parallel programming. Almost all of the algorithms presented are new and recent and are based on articles of the authors that have been published in high-level journals with high impact factors.Chapter 5 introduces a recent simulator, CupCarbon, to test and visualize the algorithms presented in the book. The scripts of their distributed versions are presented, commented and explained.The last chapter shows some real applications and problems solved by polygonal hull determination, such as finding the boundary nodes of a wireless sensor network, the area which is not covered by the nodes of a wireless sensor network, and drawing contours of a zone of interest in an image. This zone can visualize a tumor within a medical image or different parts of a fingerprint. Another application shows how the polygonal envelope can be used to extract clusters with complex shapes from a 2D data set. The very reduced complexity of the algorithm also allows it to be used in the context of Big Data. Finally, the book can open many new fields in WSNs and IoT domains, especially in cases where the presented algorithms are generalized to n dimensions.I am convinced that the tools presented in this book will certainly bring a new vision to address many issues in several fields, such as Big Data, Security, Graph Theory, Geometric Topology, Image Processing, etc. Therefore, I deeply recommend this book.-Professor Tari Abdelkamel, University of BejaiaComputational geometry techniques are highly required in solving some problems of wireless networks, like topology construction, routing etc. Being someone in the wireless Communication domain, I find lot of algorithmic, geometric, and graph related issues, especially in wireless sensor networks and IoT (Internet of Things), or in any centralized or distributed system architectures. Boundaries and Hulls of Euclidean Graphs: From Theory to Practice presents concepts and algorithms for finding convex, concave, and polygon hulls of Euclidean graphs. As mentioned in the preface of the text, the book is intended for readers that need to determine the boundary of a set of nodes that can be represented as a network, generally as a connected Euclidean graph. Later, a wireless communication engineer can test for practical coverage ranges and transmission power requirements in this topology. Starting from fundamentals on graphs and computational geometry, and fundamentals on Hulls of point set and graphs, the book progresses to various algorithms applicable to centralized and distributed architectures. The CupCarbon simulator is the key topic in the book, representing original contributions of the authors. The material presented in the book is up-to-date and meets the state-of-the-art requirements of modern networks. The book is useful for researchers and academics. The systematic presentation flow, nice organization with mathematical aspects make it more attractive. I would like to congratulate the authors for their wonderful efforts to create such a nice piece of literature with fundamentals leading to practice.-Upena Dalal, Sardar Vallabhbhai National Institute of TechnologyThis book presents a series of algorithms for the determination of the boundary nodes and the polygonal envelope of a Euclidean graph. It is a great addition to the scarce literature that deals with this problem in an algorithmic way. Most of the existing literature focuses on practical boundary determination cases, e.g. in sensor networks, where the proposed methods are often heuristics. This book proposes algorithms based on geometry where the polygonal envelope is determined using angles formed by adjacent edges of a graph. The key addition in this book is the LPCN algorithm and its decentralised version D-LPCN. The book has six chapters that build up the reader’s knowledge in this field. The first chapter introduces basic notions on graphs and computational geometry. Chapter 2 presents the concepts of convex and polygonal hulls are presented. The novelty of this chapter lies in the presentation of the different forms of the polygonal hull and their mathematical models. Chapters 3 and 4 present the algorithms to determine the convex and polygonal hulls of Euclidean graphs. These algorithms are presented in their centralized and distributed form. Chapter 5 introduces a simulation tool to test and visualize the algorithms presented in the book. The last chapter shows some applications and real-life problems solved by polygonal hull determination, such as finding the boundary nodes of a wireless sensor network, the area which is not covered by the nodes of a wireless sensor network, and drawing contours of a zone of interest in an image. The tools presented in this book will certainly bring a new perspective to address many research issues in several fields, such as big data, cyber security, graph theory, geometric topology, image processing, amongst others. I highly recommend this book to readers at all levels who are interested in the boundary nodes detection problem, the unique hands on approach will give the readers the level of understanding that they need to innovate in this domain.-Mohammad Hammoudeh, Manchester Metropolitan University