Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas

DOI10.1016/0020-0190(95)00132-VMaRDI QIDQ672261zbMATH OpenOpenAlexFDO

Authors Olivier Devillers, Mordecai J. Golin

Publication date 28 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(95)00132-v

zbMATH Keywords

AlgorithmsCirclesComputational geometryConvex hullsLower envelopesParabolas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• The complexity of incremental convex hull algorithms in \(R^ d\)
• A convex hull algorithm for discs, and applications
• An approximate algorithm for computing multidimensional convex hulls
• On computing the convex hull of (piecewise) curved objects
• An algorithm for the construction of convex hulls in simple integer recourse programming
• New approximation algorithms for minimum enclosing convex shapes
• A new algorithm for computing the convex hull of a planar point set
• A sublogarithmic convex hull algorithm
• Computing uniform convex approximations for convex envelopes and convex hulls

Cites work

• A convex hull algorithm for discs, and applications
• Some dynamic computational geometry problems

Cited in

(8)

• Minimal surface convex hulls of spheres
• Separability by two lines and by nearly straight polygonal chains
• Near optimal minimal convex hulls of disks
• QuickhullDisk: a faster convex hull algorithm for disks
• Separating objects in the plane by wedges and strips
• The rectilinear convex hull of line segments
• A novel algorithm for finding convex hull of a generic polygon with simulation of progressively supporting elastic lines
• Time-optimal computation of the rectilinear convex hull with arbitrary orientation of sets of segments and circles

This page was built for publication: Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672261)