Zhenyu Li
ABSTRACT
One useful generalization of the convex hull of a set S of points is the ε-strongly convex δ-hull. It is defined to be a convex polygon Rgr; with vertices taken from S such that no point in S lies farther than δ outside Rgr; and such that even if the vertices of Rgr; are perturbed by as much as ε, Rgr; remains convex. It was an open question as to whether an ε-strongly convex Ο(ε)-hull existed for all positive ε. We give here an Ο(n log n) algorithm for constructing it (which thus proves its existence). This algorithm uses exact rational arithmetic. We also show how to construct an ε-strongly convex Ο(ε + μ)-hull in Ο(n log n) time using rounded arithmetic with rounding unit μ. This is the first rounded arithmetic convex hull algorithm which guarantees a convex output and which has error independent of n.
- 1.Steven Fortune. Stable Maintenance of Point-Set Triangulation in Two Dimensions. In 30th Annual $ymposiem on the Foundations of Computer Science, IEEE, October 1989.Google Scholar
- 2.Ronald Graham. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters, 1:132-133, 1972.Google ScholarCross Ref
- 3.Leonidas Guibas, David Salesin, and Jorge Stolfi. Epsilon Geometry: Building Robust Algorithms from Imprecise Computations. In Proceedings of the Symposium on Computational Geometry, pages 208-217, ACM, July 1989. Google ScholarDigital Library
- 4.Victor Milenkovic. Calculating approximate curve arrangements using rounded arithmetic. In Pro. ~eedings of the Symposium on Computational Geometry, ACM, pages 197-207, June 1989. Google ScholarDigital Library
- 5.Victor Milenkovic. Double Precision Geometry: A General Technique for Calculating Line and Segment Intersections Using Rounded Arithmetic. In 30th Annual Symposium on the Foundations of Computer Science, IEEE, October 1989.Google Scholar
- 6.Victor J. Milenkovic. Verifiable Implementation8 of Geometric Alqorithms using Finite Precision Arithmetic. Ph.D. Thesis, Carnegie-Mellon, 1988. Technical Report CMU-CS-88-168, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, July 1988. Google ScholarDigital Library
- 7.Kokichi Sugihara and Masao Iri. Construction of the Voronoi Diagram for One Million Generators in Single-Precision Arithmetic Presented at First Canadian Conference on Computational Geometry, August 21-25, 1989, Montreal, Canada. Available as preprint, Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113, Japan.Google Scholar
Index Terms
- Constructing strongly convex hulls using exact or rounded arithmetic
Recommendations
The quickhull algorithm for convex hulls
The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull algorithm with the general-dimension Beneath-Beyond Algorithm. It ...
Constructing strongly convex hulls using exact or rounded arithmetic
AbstractOne useful generalization of the convex hull of a setS ofn points is the ɛ-strongly convex δ-hull. It is defined to be a convex polygon with vertices taken fromS such that no point inS lies farther than δ outside ...
Convex hulls of spheres and convex hulls of disjoint convex polytopes
Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
Comments