Linear approximation of simple objects
Published
Journal Article
Let P = {P1, P2, . . . , Pm} be a set of m convex polygons in the plane with a total number of n vertices, and for 1 ≤ i ≤ m, let wi ∈ℝ+ be a weight associated with Pi. The weighted distance between a line l and a polygon Pi is given by d(l, Pi) = minp∈Pi,q∈l d(p, q).wi, where d(p, q) is the Euclidean distance between p and q. We want to compute a line l that minimizes the maximum distance between l and the polygons of P. We present an O(nα(n) log3 n)-time algorithm to compute such a line. We also give an O(n2+ε)-time algorithm, where ε is an arbitrarily small positive constant, to solve the three dimensional version of this problem; here, P is a set of convex polytopes in ℝ3, and we want to compute a plane h that minimizes the maximum weighted distance between h and the polytopes. © 1997 Published by Elsevier Science B.V.
Full Text
Duke Authors
Cited Authors
- Varadarajan, KR; Agarwal, PK
Published Date
- April 28, 1997
Published In
Volume / Issue
- 62 / 2
Start / End Page
- 89 - 94
International Standard Serial Number (ISSN)
- 0020-0190
Digital Object Identifier (DOI)
- 10.1016/s0020-0190(97)00049-5
Citation Source
- Scopus