COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS

DOI10.1142/S0218195991000025zbMath0724.68088OpenAlexW2128830892MaRDI QIDQ3212329

Jack Scott Snoeyink, J. E. Hershberger, Leonidas J. Guibas

Publication date: 1991

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195991000025

zbMATH Keywords

convex hullcommon tangentscompact interval tree

Mathematics Subject Classification ID

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

Related Items (13)

Minimization and maximization versions of the quadratic travelling salesman problem ⋮ Ray shooting in polygons using geodesic triangulations ⋮ Approximating points by a piecewise linear function ⋮ Computing common tangents without a separating line ⋮ Cartographic line simplication and polygon CSG formulae in O(n log* n) time ⋮ Dynamic convex hulls under window-sliding updates ⋮ Efficient algorithms for the one-dimensional \(k\)-center problem ⋮ Applications of a semi-dynamic convex hull algorithm ⋮ Improved bounds for wireless localization ⋮ An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT ⋮ Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time ⋮ On Top-k Weighted<scp>Sum</scp>Aggregate Nearest and Farthest Neighbors in the L1 Plane ⋮ COMPUTING CONSTRAINED SHORTEST SEGMENTS: BUTTERFLY WINGSPANS IN LOGARITHMIC TIME

This page was built for publication: COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS