COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS
From MaRDI portal
Publication:3212329
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
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)
Related Items
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