Aspect-Ratio Voronoi Diagram with Applications

This paper considers a problem of finding an optimal point within a polygon P in the sense that when we connect the point to every vertex of P by straight line then the worst aspect ratio among all resulting triangles is optimized. This problem has an important application to triangular mesh improvement. We propose three different approaches toward this problem. The first one is based on some new Voronoi diagram defined by an aspect ratio, which is interesting in itself. The second approach is essentially a binary search defined by geometric intersection. The third one is grid-based heuristic, which might be practically best but has no theoretical guarantee on its performance.