An Output-Sensitive Convex Hull Algorithm for Planar Objects
From MaRDI portal
Publication:4513200
DOI10.1142/S0218195998000047zbMath0957.68118OpenAlexW2132847202MaRDI QIDQ4513200
Franck Nielsen, Mariette Yvinec
Publication date: 7 November 2000
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218195998000047
Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (11)
LOCATING AN OBNOXIOUS LINE AMONG PLANAR OBJECTS ⋮ Improved algorithms for the farthest colored Voronoi diagram of segments ⋮ Three problems about simple polygons ⋮ Convex hulls of spheres and convex hulls of disjoint convex polytopes ⋮ On computing the convex hull of (piecewise) curved objects ⋮ Planar lower envelope of monotone polygonal chains ⋮ Output-sensitive peeling of convex and maximal layers ⋮ Computing pseudotriangulations via branched coverings ⋮ An algorithmic toolbox for network calculus ⋮ Dynamic data structures for fat objects and their applications ⋮ An exact and efficient approach for computing a cell in an arrangement of quadrics
Cites Work
- Finding the upper envelope of n line segments in O(n log n) time
- Optimal parallel algorithms for computing convex hulls and for sorting
- On ray shooting in convex polytopes
- Convex hulls of objects bounded by algebraic curves
- Computational geometry in a curved world
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- The upper envelope of piecewise linear functions: Algorithms and applications
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Finding the convex hull of a simple polygon in linear time
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Improved lower bounds on the length of Davenport-Schinzel sequences
- A linear algorithm for finding the convex hull of a simple polygon
- A convex hull algorithm for discs, and applications
- Helly-type theorems and generalized linear programming
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- On the identification of the convex hull of a finite set of points in the plane
- Ray Shooting and Parametric Search
- An $O(n\log ^2 h)$ Time Algorithm for the Three-Dimensional Convex Hull Problem
- Finding the convex hull facet by facet
- The Ultimate Planar Convex Hull Algorithm?
- Convex hulls of piecewise-smooth Jordan curves
- Linear Optimization Queries
- An Algorithm for Convex Polytopes
- Finding the convex hull of a simple polygon
This page was built for publication: An Output-Sensitive Convex Hull Algorithm for Planar Objects
