Towards in-place geometric algorithms and data structures

DOI10.1145/997817.997854zbMath1374.68646MaRDI QIDQ5361676

Eric Y. Chen, Timothy M. Chan, Hervé Brönnimann

Publication date: 29 September 2017

Published in: Proceedings of the twentieth annual symposium on Computational geometry (Search for Journal in Brave)

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

zbMATH Keywords

Voronoi diagrams; range searching; convex hulls; in-place algorithms

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68P05: Data structures

Related Items

Optimal In-place Algorithms for Basic Graph Problems, A Framework for In-place Graph Algorithms, Geometric Streaming Algorithms with a Sorting Primitive, Reprint of: Memory-constrained algorithms for simple polygons, Prune-and-search with limited workspace, Memory efficient algorithms for cactus graphs and block graphs, In-place algorithm for erasing a connected component in a binary image, An in-place algorithm for Klee's measure problem in two dimensions, In-place algorithms for computing (Layers of) maxima, Space-efficient geometric divide-and-conquer algorithms, Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection, Time-space trade-offs for triangulations and Voronoi diagrams, Variations of largest rectangle recognition amidst a bichromatic point set, Frameworks for designing in-place graph algorithms, Rectilinear path problems in restricted memory setup, Line-segment intersection made in-place, Memory-constrained algorithms for simple polygons, Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time, Computing (and Life) Is All about Tradeoffs, Succinct and Implicit Data Structures for Computational Geometry, Time-Space Trade-offs for Triangulations and Voronoi Diagrams