LPCN: Least Polar-angle Connected Node Algorithm to Find a Polygon Hull in a Connected Euclidean Graph

Autor: Massinissa Saoudi, Madani Bezoui, Reinhardt Euler, Marc Sevaux, Farid Lalem, M. Tahar Kechadi, Ahcène Bounceur
Přispěvatelé: Lab-STICC_UBO_CACS_MOCS, Université de Brest (UBO)-Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), Université M'Hamed Bougara Boumerdes (UMBB), Lab-STICC_UBO_CID_DECIDE, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Lab-STICC_UBS_CID_DECIDE, École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT), ANR-14-CE24-0017,PERSEPTEUR,PlateformE viRtuelle 3D pour la Simulation des rEseaux de caPTEURs(2014), Université M'Hamed Bougara Boumerdes
Jazyk: angličtina
Rok vydání: 2017
Předmět:
Vertex (graph theory)
Convex hull
Computer Networks and Communications
Computer science
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
02 engineering and technology
Biconnected graph
Simplex graph
Computational geometry
law.invention
Planar graph
symbols.namesake
law
Euclidean geometry
String graph
Line graph
0202 electrical engineering
electronic engineering
information engineering
Shape reconstruction
[INFO]Computer Science [cs]
Lattice graph
Complement graph
Distance-hereditary graph
Connected component
Degree (graph theory)
Visibility graph
020206 networking & telecommunications
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Butterfly graph
Graph
Computer Science Applications
Vertex (geometry)
Hardware and Architecture
Polygon hull
Cycle graph
Polygon
symbols
k-edge-connected graph
020201 artificial intelligence & image processing
Output-sensitive algorithm
Regular graph
Index Terms-Connected Euclidean graph
Boundary nodes
Algorithm
Zdroj: Journal of Network and Computer Applications (JNCA)
Journal of Network and Computer Applications (JNCA), Elsevier, 2017, ⟨10.1016/j.jnca.2017.05.005⟩
JNCA, Journal of Network and Computer Applications
JNCA, Journal of Network and Computer Applications, 2017, ⟨10.1016/j.jnca.2017.05.005⟩
ISSN: 1084-8045
1095-8592
DOI: 10.1016/j.jnca.2017.05.005⟩
Popis: Finding the polygon hull in a connected Euclidean graph can be considered as the problem of finding the convex hull with the exception that at any iteration a vertex can be chosen only if it is connected to the vertex chosen at the previous iteration. One of the methods that can be used for this kind of problems is Jarvis' algorithm which allows to find the convex hull and which must be adapted because it does not take into account the connections of the nodes. In this paper, we propose a new algorithm that chooses for a current node and among its neighbors in the graph the nearest polar angle node with respect to the node found in the previous iteration. Its complexity is O ( gh 2 ) , where g is the maximum degree of the graph and h the number of the nodes on the hull. For ease of presentation, we first identify some specific graph-structures whose presence may lead a basic version of the algorithm to fail, and we then show how to modify that version to obtain a procedure of the given complexity. Finally, we present some practical applications that can be resolved using the proposed algorithm.
Databáze: OpenAIRE
Externí odkaz: