Cuttings for disks and axis-aligned rectangles in three-space

DOI10.1007/s00454-009-9158-2zbMath1195.68109MaRDI QIDQ848675

Diane L. Souvaine, Csaba D. Tóth, Eynat Rafalin

Publication date: 4 March 2010

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-009-9158-2

zbMATH Keywords

spanning tree; computational geometry; cuttings; binary space partition; simplicial partition

Mathematics Subject Classification ID

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

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

68P05: Data structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On counting pairs of intersecting segments and off-line triangle range searching
• Sharp bounds for vertical decompositions of linear arrangements in four dimensions
• A deterministic view of random sampling and its use in geometry
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Efficient binary space partitions for hidden-surface removal and solid modeling
• \(\epsilon\)-nets and simplex range queries
• Cutting hyperplane arrangements
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• Cutting hyperplanes for divide-and-conquer
• The Min-Max Spanning Tree Problem and some extensions
• Spanning trees crossing few barriers
• Applications of random sampling in computational geometry. II
• Quasi-optimal range searching in spaces of finite VC-dimension
• Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles
• Vertical decompositions for triangles in 3-space
• Counting and representing intersections among triangles in three dimensions
• Almost tight upper bounds for vertical decompositions in four dimensions
• Optimal binary space partitions for orthogonal objects
• A randomized linear-time algorithm to find minimum spanning trees
• Topology for Computing
• On Point Location and Motion Planning among Simplices
• The Clarkson–Shor Technique Revisited and Extended
• Binary Space Partitions for Fat Rectangles
• Curve-Sensitive Cuttings
• Algorithms - ESA 2003