ABSTRACT
During the 1970s, an important number of methods has been proposed for finding the convex hull of a set of points. In 1972, Graham was the first to propose a technique based on scanning points from right to left. One year after, Jarvis proposed a new technique based on polar angles, and then a number of other methods have been published including Andrew, Kallay, Chan, etc. Some of these algorithms are presented in Section 3.1. If the problem of finding the convex hull attracted the curiosity of several researchers, unfortunately, this is not the case for concave and polygon hulls. In Section 3.2, we present some of the existing algorithms for the construction of a concave hull. Finally, Sections 3.3 and 3.4 address some new algorithms for finding a polygon hull in connected Euclidean graphs like the LPCN algorithm. We present several versions of LPCN that can be applied to different types of the considered graphs. We conclude with a new algorithm, called RR-LPCN, which has been designed for the same purpose, but for which it is not necessary to specify the starting node.
