Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection

DOI10.1145/1542362.1542376MaRDI QIDQ5370702zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan, Eric Y. Chen

Publication date 20 October 2017

Published in Proceedings of the twenty-fifth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1542362.1542376

zbMATH Keywords

convex hullsVoronoi diagramscache-oblivious algorithmsin-place algorithmssegment intersection

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• Line-segment intersection made in-place
• scientific article; zbMATH DE number 2086251
• Instance-optimal geometric algorithms
• Towards in-place geometric algorithms and data structures

Cited in

(6)

• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• Optimal time-space tradeoff for the 2D convex-hull problem
• Instance-optimal geometric algorithms
• Partial sums on the ultra-wide word RAM
• Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm
• scientific article; zbMATH DE number 2086251 (Why is no real title available?)

This page was built for publication: Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection

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