The first algorithm for finding one of these structures for simple inputs in less than n log n was given by  Tarjan and Van Wyk.
The first algorithm for finding one of these structures for simple inputs in less than n log n was given by  Tarjan and Van Wyk. The Gabriel graph is a subgraph of one special type of these structures. Mirante's  method for doing this connects the outer edges in a radial fashion. A common way to do this is to first perform a y  monotone decomposition and then find this for the montone structures in linear time. The solution to the Art Gallery  Problem performs a coloring on one of these structures created from the problem description. The Voronoi diagram  is the dual for one type of these solutions on a set of points. In the Delaunay type of these structures, no points are  located within the circumcircles. For 10 points, name these decompositions of a polygon into maximal non-  intersecting diagonals that form certain three sided shapes.
The first algorithm for finding one of these structures for simple inputs in less than n log n was given by  Tarjan and Van Wyk.
triangulations