| 講演抄録／キーワード |
| 講演名 |
2006-04-26 10:50
Polygonal Curve Approximation Using Grid Points with Application to a Triangular Mesh Generation with Small Number of Different Edge Lengths
○Shin-ichi Tanigawa・Naoki Katoh（Kyoto Univ.） |
| 抄録 |
（和） |
各辺長が$\underline{l}$以上、$2\underline{l}$以下で与えられた$x$単調な折れ線を入力とした時、これを与えられた正方形グリッドの頂点のみを用いて長さ$\underline{l}$以上、$\beta\underline{l}$以下の近似誤差が最小であるような折れ線へと近似することを考える。まず初めにグリッドの位置が固定の場合に対して、グリッドの頂点を用いた誤差最小の折れ線近似を$O((n/\alpha^4)\log(n/\alpha))$時間で求めるアルゴリズムを提案する。ここで$\alpha$は$0<\alpha<1$で与えられたグリッド幅を表すパラメータである。このアルゴリズムを基に、グリッドが固定されていない場合を考え、最適なグリッド配置と誤差最小の折れ線を同時に求める$O((n^3/\alpha^{12})\log^2(n/\alpha))$時間のアルゴリズムを提案する。 |
| （英） |
For a given $x$-monotone polygonal curve each of whose edge lengths is between $\underline{l}$ and $2\underline{l}$,
we consider the problem of approximating it by another $x$-monotone polygonal curve using points of a square grid so that there exists a small number of different edge lengths and every edge length is between $\underline{l}$ and $\beta \underline{l}$, where $\beta$ is a given parameter satisfying $1\leq \beta \leq 2$. Our first algorithm computes an approximate polygonal curve using fixed square grid points in $O((n/\alpha^4)\log(n/\alpha))$ time. Based on this, our second algorithm finds an approximate polygonal curve as well as an optimal grid placement simultaneously in $O((n^3/\alpha^{12})\log^2(n/\alpha))$ time,
where $\alpha$ is a parameter that controls the closeness of approximation. Based on the approximate polygonal curve,
we shall give an algorithm for finding a uniform triangular mesh for an $x$-monotone polygon with a constant number of different edge lengths. |
| キーワード |
（和） |
計算幾何学 / 折れ線近似 / アレンジメント / ボロノイ図 / / / / |
| （英） |
computational geometry / polygonal curve approximation / arrangement / Voronoi diagram / / / / |
| 文献情報 |
信学技報, vol. 106, no. 29, COMP2006-3, pp. 17-24, 2006年4月. |
| 資料番号 |
COMP2006-3 |
| 発行日 |
2006-04-19 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|