An output sensitive algorithm for discrete convex hulls

DOI10.1016/S0925-7721(97)00031-XMaRDI QIDQ1388138zbMATH OpenFDO

Authors Sariel Har-Peled

Publication date 8 June 1998

Published in Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

convex hulldiscrete hull

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• An Output-Sensitive Convex Hull Algorithm for Planar Objects
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm
• Output-sensitive results on convex hulls, extreme points, and related problems
• Optimal, output-sensitive algorithms for constructing planar hulls in parallel
• An approximate algorithm for computing multidimensional convex hulls
• Incremental convex hull algorithms are not output sensitive
• Incremental convex hull algorithms are not output sensitive
• Derandomizing an output-sensitive convex hull algorithm in three dimensions
• A convex hull algorithm for discs, and applications

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 589497 (Why is no real title available?)
• A Lower Bound for the Volume of Strictly Convex Bodies with many Boundary Lattice Points
• A linear algorithm for determining the separation of convex polyhedra
• Data Structures for Retrieval on Square Grids
• On the number of convex lattice polytopes
• SUBPIXEL IMAGE REGISTRATION USING CIRCULAR FIDUCIALS

Cited in

(13)

• Efficient Computation of the Outer Hull of a Discrete Path
• Lyndon + Christoffel = digitally convex
• scientific article; zbMATH DE number 1796959 (Why is no real title available?)
• Output-Sensitive Construction of the Union of Triangles
• Output sensitive algorithms for approximate incidences and their applications
• On the complexity of randomly weighted multiplicative Voronoi diagrams
• Guarding galleries and terrains
• Region-fault tolerant geometric spanners
• Euclidean farthest-point Voronoi diagram of a digital edge
• An oracle-based, output-sensitive algorithm for projections of resultant polytopes
• On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm
• An Output-Sensitive Convex Hull Algorithm for Planar Objects
• QuickhullDisk: a faster convex hull algorithm for disks

This page was built for publication: An output sensitive algorithm for discrete convex hulls

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