On Finding Large Polygonal Voids Using Delaunay Triangulation: The Case of Planar Point Sets

Abstract

In astronomy, the objective determination of large empty spaces or voids in the spatial distribution of galaxies is part of the characterization of the large scale structure of the universe. This paper proposes a new method to find voids that starting from local longest-edges in a Delaunay triangulation builds the largest possible empty or almost empty polygons around them. A polygon is considered a void if its area is larger than a threshold value. The algorithm is validated in 2D points with artificially generated circular and non-convex polygon voids. Since the algorithm naturally extends to 3D, preliminary results in 3D are also shown.