✦ LIBER ✦

Approximating Polygonal Curves in Two and Three Dimensions

✍ Scribed by Kento Miyaoku; Koichi Harada

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 134 KB
Volume: 60
Category: Article
ISSN: 1077-3169
DOI: 10.1006/gmip.1997.0468

No coin nor oath required. For personal study only.

✦ Synopsis

We discuss the weighted minimum number polygonal approximation problem. Eu and Toussaint (1994, CVGIP: Graphical Models Image Process. 56, 231-246) considered this problem subject to the parallel-strip error criterion in R 2 with L q distance metrics, and they concluded that it can be solved in O(n 2 ) time by using the Cone intersection method. In this note, we clarify part of their discussion and show that solving their problem correctly requires O(n 2 log n) time. Also, we discuss the weighted minimum number problem subject to the line segment error criterion. When input curves are strictly monotone in R 3 , we demonstrate that if the L 1 or L ∞ metric is used, this problem also can be solved in O(n 2 ) time.

📜 SIMILAR VOLUMES

Polygons in Three Dimensions

✍ Prabir Bhattacharya; Azriel Rosenfeld 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 482 KB

Three-level BDDC in two dimensions

✍ Xuemin Tu 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

Optimal Pose Estimation in Two and Three

Optimal Pose Estimation in Two and Three Dimensions

✍ S.H. Joseph 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 307 KB

This paper concerns the problem of pose estimation, in particular the application of linear and nonlinear methods to the case of anisotropic error distributions. Incremental and batch techniques are discussed, and a linear solution to the two dimensional problem is developed by reference to the nois

Comparing Planetary Accretion in Two and

Comparing Planetary Accretion in Two and Three Dimensions

✍ J.E. Chambers 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 366 KB

Two ways to speed up N-body simulations of planet formation are (i) to confine motion to 2 spatial dimensions, or (ii) to artificially enhance the physical radii of the bodies. These short cuts have the same effect of increasing the collision probability between objects. Here, I compare the results

Approximating second-order vector differ

Approximating second-order vector differential operators on distorted meshes in two space dimensions

✍ F. Hermeline 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 259 KB

Efficiently Approximating the Minimum-Vo

Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions

✍ Gill Barequet; Sariel Har-Peled 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 221 KB

We present an efficient O n + 1/ε 4 5 -time algorithm for computing a 1 + ε)approximation of the minimum-volume bounding box of n points in 3 . We also present a simpler algorithm whose running time is O n log n + n/ε 3 . We give some experimental results with implementations of various variants of