|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/9518
|
| タイトル: | Optimal Triangulations of points and segments with steiner points |
| 著者: | Aronov, Boris
Asano, Tetsuo
Funke, Stefan |
| キーワード: | Computational geometry
constrained Delaunay triangulation
polynomial-time algorithm
Steiner point
Voronoi diagram |
| 発行日: | 2010-02 |
| 出版者: | World Scientific Publishing |
| 誌名: | International Journal of Computational Geometry and Applications |
| 巻: | 20 |
| 号: | 1 |
| 開始ページ: | 89 |
| 終了ページ: | 104 |
| DOI: | 10.1142/S0218195910003219 |
| 抄録: | 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. |
| Rights: | Electronic version of an article published as International Journal of Computational Geometry and Applications, 20(1), 2010, 89-104. DOI:10.1142/S0218195910003219. Copyright World Scientific Publishing Company, http://dx.doi.org/10.1142/S0218195910003219 |
| URI: | http://hdl.handle.net/10119/9518 |
| 資料タイプ: | author |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| 15870-1.pdf | | 558Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
