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.

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

Citation Source

  • Scopus