Optimal Triangulations of points and segments with steiner points
スポンサーリンク
概要
- 論文の詳細を見る
Consider a set X of points in the plane and a set E of non-crossing segments with endpoints in X. One can efficiently compute the triangulation of the convex hull of the points, which uses X as the vertex set, respects E, and maximizes the minimum internal angle of a triangle. In this paper we consider a natural extension of this problem: Given in addition a Steiner point p, determine the optimal location of p and a triangulation of X ∪ {p} respecting E, which is best among all triangulations and placements of p in terms of maximizing the minimum internal angle of a triangle. We present a polynomial-time algorithm for this problem and then extend our solution to handle any constant number of Steiner points.
論文 | ランダム
- 世界と日本を結ぶ--人流とその魅力を探る 中欧の三都の一つハンガリー・ブダペスト
- 中欧進出企業がみるビジネス環境--ワルシャワ,ブダペスト,プラハ発 (中欧経済のダイナミズム--ポーランド,ハンガリー,チェコ〜活発化する外資の進出)
- 世界主要国繊維産業の近況--ITMFカントリー・ステートメント(2001年) (国際繊連ブダペスト総会)
- ITMFブダペスト総会報告 テキスタイルの新しいマーケティング環境 (国際繊連ブダペスト総会)
- 国際繊連ブダペスト総会