A sweep-line algorithm that accomplishes this process via a divide-and-conquer strategy with a computational complexity of O(n log n) was developed by Garey.
A sweep-line algorithm that accomplishes this process via a divide-and-conquer strategy with a computational complexity of O(n log n) was developed by Garey. Tarjan and van Wyk reduced this complexity to O(n log log n) by reducing the problem of performing this process to the problem of computing the horizontal visibility map. Fisk used this process, followed by a 3-coloring, to give a short proof of Chvatal's art gallery theorem. Chazelle demonstrated a linear time method for performing this operation (*) on a simple polygon , and a method for carrying out this process such that the result satisfies the empty circumcircle property was developed by Delaunay. For a simple and convex polygon, this can be trivially performed by picking a vertex and drawing a line to every other vertex not adjacent to the chosen one. For 10 points, identify this procedure of subdividing a surface into 2-simplexes whose angles sum to 180 degrees.
A sweep-line algorithm that accomplishes this process via a divide-and-conquer strategy with a computational complexity of O(n log n) was developed by Garey.
triangulation [accept descriptions like "dividing a surface into triangles" before "subdividing" is mentioned]