COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS

DOI10.1142/S0218195991000025zbMATH Open0724.68088OpenAlexW2128830892MaRDI QIDQ3212329FDOQ3212329

Authors: Jack Snoeyink, Leonidas Guibas, John Hershberger 

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

Recommendations

• Connected component and simple polygon intersection searching
• Connected component and simple polygon intersection searching
• scientific article; zbMATH DE number 1617248
• Dynamic planar convex hull operations in near-logarithmic amortized time
• Storing line segments in partition trees

zbMATH Keywords

convex hullcommon tangentscompact interval tree

Mathematics Subject Classification ID

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

Cited In (15)

• Dynamic convex hulls under window-sliding updates
• Improved bounds for wireless localization
• Computing common tangents without a separating line
• Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time
• Efficient algorithms for the one-dimensional \(k\)-center problem
• Approximating points by a piecewise linear function
• Algorithms for subpath convex hull queries and ray-shooting among segments
• Ray shooting in polygons using geodesic triangulations
• Cartographic line simplication and polygon CSG formulae in \(O(n \log^* n)\) time
• On top-\(k\) weighted sum aggregate nearest and farthest neighbors in the \(L_1\) plane
• An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT
• Title not available (Why is that?)
• COMPUTING CONSTRAINED SHORTEST SEGMENTS: BUTTERFLY WINGSPANS IN LOGARITHMIC TIME
• Applications of a semi-dynamic convex hull algorithm
• Minimization and maximization versions of the quadratic travelling salesman problem

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

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