Space-efficient geometric divide-and-conquer algorithms

DOI10.1016/j.comgeo.2006.03.006zbMath1185.68772OpenAlexW2114400222WikidataQ57009406 ScholiaQ57009406MaRDI QIDQ883238

Jan Vahrenhold, Pat Morin, Jason Morrison, Prosenjit Bose, Anil Maheshwari, Michiel H. M. Smid

Publication date: 4 June 2007

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2006.03.006

zbMATH Keywords

in-place algorithmsspace-efficient algorithmsin situ algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (10)

An in-place algorithm for Klee's measure problem in two dimensions ⋮ In-place algorithms for computing (Layers of) maxima ⋮ Line-segment intersection made in-place ⋮ Variations of largest rectangle recognition amidst a bichromatic point set ⋮ Prune-and-search with limited workspace ⋮ Memory efficient algorithms for cactus graphs and block graphs ⋮ Unnamed Item ⋮ Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection ⋮ Intersections and circuits in sets of line segments ⋮ Rectilinear path problems in restricted memory setup

Uses Software

• Find

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stable minimum space partitioning in linear time
• Sorting multisets stably in minimum space
• Time bounds for selection
• Applications of random sampling in computational geometry. II
• Towards in-place geometric algorithms and data structures
• LATIN 2004: Theoretical Informatics
• Asymptotically efficient in-place merging

This page was built for publication: Space-efficient geometric divide-and-conquer algorithms