COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS

DOI10.1142/S0218195991000025MaRDI QIDQ3212329zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

common tangentscompact interval treeconvex hull

Mathematics Subject Classification ID

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

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

Cited in

(20)

• Applications of a semi-dynamic convex hull algorithm
• Cartographic line simplification and polygon CSG formulae in O(n^* n) time
• Ray shooting in polygons using geodesic triangulations
• Approximating points by a piecewise linear function
• scientific article; zbMATH DE number 5606397 (Why is no real title available?)
• COMPUTING CONSTRAINED SHORTEST SEGMENTS: BUTTERFLY WINGSPANS IN LOGARITHMIC TIME
• An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT
• Efficient algorithms for the one-dimensional \(k\)-center problem
• Computing common tangents without a separating line
• 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
• Minimization and maximization versions of the quadratic travelling salesman problem
• Dynamic convex hulls under window-sliding updates
• Algorithms for subpath convex hull queries and ray-shooting among segments
• Dynamic convex hulls for simple paths
• Dynamic convex hulls under window-sliding updates
• Augmenting plane straight-line graphs to meet parity constraints
• A new algorithm for Euclidean shortest paths in the plane
• Dynamic convex hulls for simple paths
• Improved bounds for wireless localization

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)