Skip to Main content Skip to Navigation
Journal articles

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

Farid Lalem Ahcène Bounceur 1, * Bezoui Madani 2 Saoudi Massinissa Reinhardt Euler 3 M. Tahar Kechadi Marc Sevaux 4
* Corresponding author
1 Lab-STICC_UBO_CACS_MOCS
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance, UBO - Université de Brest
3 Lab-STICC_UBO_CID_DECIDE
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
4 Lab-STICC_UBS_CID_DECIDE
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
Abstract : 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(gh2), 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.
Complete list of metadatas

Cited literature [40 references]  Display  Hide  Download

https://hal.univ-brest.fr/hal-01519491
Contributor : Ahcène Bounceur <>
Submitted on : Friday, March 13, 2020 - 1:56:09 PM
Last modification on : Wednesday, June 24, 2020 - 4:19:43 PM
Document(s) archivé(s) le : Sunday, June 14, 2020 - 2:07:02 PM

File

lpcn_algorithm-1.pdf
Files produced by the author(s)

Identifiers

Citation

Farid Lalem, Ahcène Bounceur, Bezoui Madani, Saoudi Massinissa, Reinhardt Euler, et al.. LPCN: Least Polar-angle Connected Node Algorithm to Find a Polygon Hull in a Connected Euclidean Graph. JNCA, Journal of Network and Computer Applications, 2017, ⟨10.1016/j.jnca.2017.05.005⟩. ⟨hal-01519491⟩

Share

Metrics

Record views

682

Files downloads

223