Recursive voids for identifying a nonconvex boundary of a set of points in the plane

• We introduce a method that identifies a nonconvex boundary of points in the plane.
• The nonconvex boundary is explored through finding empty regions recursively.
• Our algorithm is output sensitive and runs in linear time.
• We use a tree structure and a phylogenic measure to determine shape complexity.
• We present results on data size, shape length, shape complexity and noise.

We introduce a method that identifies the boundary of a nonconvex shape of a set of points in the plane. The boundary of the shape is explored through finding empty regions recursively within a shell that encapsulates all of the points. Our algorithm is output sensitive and runs in linear O(ℓn)O(ℓn) time determined by the output parameter ℓℓ, which is proportional to the length of the nonconvex boundary measured by a threshold unit distance. The recursive nature of our algorithm allows a tree structure that characterizes the empty regions, and by complementarity, the nonconvex shape itself. We use a distance measure based on lowest common ancestor of a pair of nodes in this tree and define the complexity of a shape as the average of the distances between all pairs. We present computational results on data size, threshold, shape complexity and noise on a set of different nonconvex shapes.