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

DOI10.1007/S00454-009-9158-2MaRDI QIDQ848675zbMATH OpenOpenAlexFDO

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

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

computational geometrycuttingsspanning treebinary space partitionsimplicial partition

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Cuttings for Disks and Axis-Aligned Rectangles
• CUTTINGS AND APPLICATIONS
• Curve-Sensitive Cuttings
• Spanning trees crossing few barriers
• Minimum cuts in geometric intersection graphs

Cites work

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

Cited in

(10)

• Optimally cutting a surface into a disk
• Minimum cuts in geometric intersection graphs
• Stabbing boxes with finitely many axis-parallel lines and flats
• Hole-Cutting for Three-Dimensional Overlapping Grids
• Curve-Sensitive Cuttings
• Curve-sensitive cuttings
• Cutting disjoint disks by straight lines
• Cutting a set of disks by a line with leaving many intact disks in both sides
• Cuttings for Disks and Axis-Aligned Rectangles
• scientific article; zbMATH DE number 2247481 (Why is no real title available?)

This page was built for publication: Cuttings for disks and axis-aligned rectangles in three-space

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