Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells |
| |
| Authors: | P. K. Agarwal B. Aronov M. Sharir |
| |
| Affiliation: | (1) Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NC 27708-0129, USA pankaj@cs.duke.edu, US;(2) Department of Computer and Information Science, Polytechnic University, Brooklyn, NY 11201-3840, USA aronov@ziggy.poly.edu, US;(3) School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel sharir@math.tau.ac.il, IL;(4) Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA, US |
| |
| Abstract: | Let S be a set of n points in reals 3 . Let opt be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S . We first present an O(n 5 ) -time algorithm for computing opt , which as far as we know is the first nontrivial algorithm for this problem. We then present an O(n 2+δ ) -time algorithm, for any δ>0 , that computes a cylindrical shell of width at most 56opt containing S . Received May 31, 2000, and in revised form October 25, 2000. Online publication August 29, 2001. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
