An in-place algorithm for Klee's measure problem in two dimensions

DOI10.1016/J.IPL.2006.12.004MaRDI QIDQ845997zbMATH OpenOpenAlexFDO

Authors Jan Vahrenhold

Publication date 29 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2006.12.004

zbMATH Keywords

analysis of algorithmscomputational geometry

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A (slightly) faster algorithm for Klee's measure problem
• A (slightly) faster algorithm for klee's measure problem
• An improved algorithm for Klee's measure problem on fat boxes
• scientific article; zbMATH DE number 1302378
• Bringing order to special cases of Klee's measure problem
• A faster optimal algorithm for the measure problem
• An optimal speedup algorithm for the measure problem
• Algorithms for \(k\)-dispersion for points in convex position in the plane
• scientific article; zbMATH DE number 1092062
• Two algorithms for approximation in highly complicated planar domains

Cites work

• Algorithms and Data Structures
• Asymptotically efficient in-place merging
• Can the Measure of ∪ n 1 [ a i , b i ] be Computed in Less Than O(n logn) Steps?
• New Upper Bounds in Klee’s Measure Problem
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• Space-efficient geometric divide-and-conquer algorithms
• Space-efficient planar convex hull algorithms
• Stable unmerging in linear time and constant space
• Towards in-place geometric algorithms and data structures

Cited in

(4)

• Klee's measure problem on fat boxes in time \(\partial(n^{(d+2)/3})\)
• An improved algorithm for Klee's measure problem on fat boxes
• Efficient transformations for Klee's measure problem in the streaming model
• Space-efficient plane-sweep algorithms

Describes a project that uses

Uses Software

• heapsort

This page was built for publication: An in-place algorithm for Klee's measure problem in two dimensions

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