carrier image

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

Hervias, Carlos, Nancy Hitschfeld-Kahler, Luis E. Campusano, and Giselle Font

22nd International Meshing Roundtable, Springer-Verlag, pp.275-292, October 13-16 2013


22nd International Meshing Roundtable
Orlando, FL
October 13-16,2013

Departamento de Astronomia, Universidad de Chile, Casilla 36-D, Santiago, Chile
Departamento de Ciencias de la Computacion, Universidad de Chile
Email: {chervias,luis}, {nancy,gfont}

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.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article