Incremental χ-shape

Peter and Matt are developing an incremental algorithm for χ-shapes, a widely used “footprint” algorithm (a shape that characterizes the distribution of a set of points). χ-shapes guarantee the regularity of the constructed polygonal shapes. The algorithm operates by iteratively removing the longest exterior edge of the triangulation of the input points such that the result does not lead to a topological irregularity. Because of this unique rule, χ-shapes are more difficult to construct incrementally than other footprints. We use a dynamic data structure to maintain the edges removed by the χ-shape algorithm. When a new set of points is inserted, or when a set of existing points is deleted, the data structure can be efficiently modified according to the changes in the Delaunay triangulation (below) to obtain the updated χ-shape. Peter is currently working on a journal paper about this work.


Tagged with:
Posted in Activites