Space-efficient geometric divide-and-conquer algorithms

DOI10.1016/J.COMGEO.2006.03.006MaRDI QIDQ883238zbMATHOpenAlexWikidataFDO

Authors Prosenjit Bose, Anil Maheshwari, Pat Morin, Jason Morrison, Jan Vahrenhold, Michiel 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)

Recommendations

• Towards in-place geometric algorithms and data structures
• Space-efficient plane-sweep algorithms
• Space-efficient planar convex hull algorithms
• Divide-and-conquer in planar geometry
• Approximations and optimal geometric divide-and-conquer

Cites work

• scientific article; zbMATH DE number 2086251 (Why is no real title available?)
• scientific article; zbMATH DE number 3569833 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Applications of random sampling in computational geometry. II
• Asymptotically efficient in-place merging
• Introduction to algorithms
• LATIN 2004: Theoretical Informatics
• Sorting multisets stably in minimum space
• Stable minimum space partitioning in linear time
• Time bounds for selection
• Towards in-place geometric algorithms and data structures

Cited in

(11)

• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• scientific article; zbMATH DE number 7561401 (Why is no real title available?)
• In-place algorithms for computing (Layers of) maxima
• Intersections and circuits in sets of line segments
• Variations of largest rectangle recognition amidst a bichromatic point set
• Space-efficient plane-sweep algorithms
• Rectilinear path problems in restricted memory setup
• An in-place algorithm for Klee's measure problem in two dimensions
• Line-segment intersection made in-place
• Memory efficient algorithms for cactus graphs and block graphs
• Prune-and-search with limited workspace

Describes a project that uses

Uses Software

• Find

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

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