Optimal Triangulation with Steiner Points
There are many ways to triangulate a simple n-gon; for certain optimization criteria such as maximization of the smallest internal angle it is known how to efficiently compute the best triangulation with respect to this criterion. In this paper we conside
- PDF / 393,139 Bytes
- 11 Pages / 430 x 660 pts Page_size
- 117 Downloads / 245 Views
Polytechnic University, Brooklyn, NY, USA School of Information Science, JAIST, Japan Max-Planck-Institut f¨ ur Informatik, Saarbr¨ ucken, Germany 2
3
Abstract. There are many ways to triangulate a simple n-gon; for certain optimization criteria such as maximization of the smallest internal angle it is known how to efficiently compute the best triangulation with respect to this criterion. In this paper we consider a natural extension of this problem: Given a simple polygon P and one Steiner point p in its interior, determine the optimal location of p and a triangulation of P and p which is best amongst all triangulations and placements of p. We present a polynomial-time algorithm for this problem when the optimization criterion is maximization of the minimum angle. Furthermore, we also provide a more general polynomial-time algorithm for finding the optimal placement of a constant number of Steiner points under the same optimization criterion.
1
Introduction
Triangulations of simple polygons arise in many applications. Some triangulation of a given simple polygon can even be computed in linear time using Chazelle’s algorithm [6]. Optimizing some criterion over all triangulations is also possible. For example, a popular optimization criterion is to maximize the minimum angle of any triangle. Such a triangulation is known as a constrained Delaunay triangulation; it can be obtained in O(n log n) time for an n-gon [7]. We could also find a minimum-weight triangulation that minimizes the total length of chords required for triangulation using dynamic programming. Dynamic programming is also powerful enough to find a triangulation in which the worst aspect ratio of resulting triangles is minimized, where the aspect ratio of a triangle is the ratio of length of the longest side to its width, i.e., its smallest height. In this paper we are interested in what happens when we allow one Steiner point in the triangulation. More precisely, given a simple polygon P , we want to find a point p in the interior of P such that the quality of the optimal triangulation of P +{p} is optimized under a given optimization criterion. If maximization of the minimum internal angle is the goal, we want to find a location of an interior point p such that the minimum angle of the optimal triangulation of P + {p} is maximized among all possible interior points p. As far as the authors know, there is no previous study of the question. Our main concern in this paper is to develop a polynomial-time algorithm. A natural extension of this problem is to allow for more Steiner points to be inserted or to use different optimization criteria for the triangulation. The T. Tokuyama (Ed.): ISAAC 2007, LNCS 4835, pp. 681–691, 2007. c Springer-Verlag Berlin Heidelberg 2007
682
B. Aronov, T. Asano, and S. Funke
extension to multiple Steiner points is not trivial at all. In fact, it seems no simple algorithm exists for finding an optimal set of Steiner points. We present a fairly involved polynomial-time algorithm that optimally places any constant number k o
Data Loading...
