Towards in-place geometric algorithms and data structures

DOI10.1145/997817.997854zbMath1374.68646MaRDI QIDQ5361676

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

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

Geometric Streaming Algorithms with a Sorting Primitive, Reprint of: Memory-constrained algorithms for simple polygons, Prune-and-search with limited workspace, 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, 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