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

DOI10.1145/1542362.1542376zbMATH Open1388.68284OpenAlexW2076089605MaRDI QIDQ5370702FDOQ5370702

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

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

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)

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
• Title not available (Why is that?)

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)