Aspect-ratio Voronoi diagram and its complexity bounds

This Letter first defines an aspect ratio of a triangle by the ratio of the longest side over the minimal height. Given a set of line segments, any point p in the plane is associated with the worst aspect ratio for all the triangles defined by the point and the line segments. When a line segment s(i) gives the worst ratio, we say that p is dominated by s(i). Now, an aspect-ratio Voronoi diagram for a set of line segments is a partition of the plane by this dominance relation. We first give a formal definition of the Voronoi diagram and give O(n(2+epsilon)) upper bound and Omega(n(2)) lower bound on the complexity, where E is any small positive number. The Voronoi diagram is interesting in itself, and it also has an application to a problem of finding an optimal point to insert into a simple polygon to have a triangulation that is optimal in the sense of the aspect ratio. (c) 2007 Elsevier B.V. All rights reserved.