The farthest point Delaunay triangulation minimizes angles (Q1188284)

It is known that for \(n\) points in the plane in general position (i.e., no four points are cocircular) the sequence of triangle angles, sorted from sharpest to last sharp, is lexicographically maximized over all such sequences constructed from triangulations of the point set. In this sense, the paper deals with duals to farthest point Voronoi diagrams of a planar point set \(P\). Considering the vertex sets of convex polygons (note that the farthest point Voronoi diagram of \(P\) has only regions corresponding to the vertices of \(\text{conv}(P)\) it is shown that for general position the sequence of triangle angles, sorted from sharpest to least sharp, is lexicographically minimized. On that base, the sharpest angle determined by three vertices can be found in linear time. The sharpest angle, determined by three of \(n\) arbitrary points, corresponds to a line segment bounding a face of the dual line arrangement and can be found in \(O(n^ 2)\) time. A faster approach would also speed up the detection of degeneracy (three collinear points or three concurrent lines) in a configuration. Detecting degeneracy faster than in quadratic time is a known open problem in computational geometry. The author hopes that alternate views on such problems (as his minimum angle approach) could lead to improvements in that direction.