Name
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 56\opt containing S . |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/s00454-001-0039-6 | Discrete & Computational Geometry |
Keywords | Field | DocType |
minimum-width cylindrical shell,approximation algorithm,connectivity,hamilton path,hamilton cycle,planar graph | Approximation algorithm,Discrete mathematics,Combinatorics,Cylinder (engine),Hamiltonian path,Cylinder,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
26 | 3 | 0179-5376 |
ISBN | Citations | PageRank |
0-89871-453-2 | 14 | 1.08 |
References | Authors | |
12 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pankaj K. Agarwal | 1 | 5257 | 593.81 |
| Boris Aronov | 2 | 1430 | 149.20 |
| Micha Sharir | 3 | 8405 | 1183.84 |