Counting and representing intersections among triangles in three dimensions

DOI10.1016/j.comgeo.2005.02.003zbMath1086.65506OpenAlexW2203294237MaRDI QIDQ2571213

Esther Ezra, Micha Sharir

Publication date: 1 November 2005

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

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

zbMATH Keywords

arrangementsalgorithm3SUM-hard problemscounting intersectionscurve-sensitive cuttingstriangles in three dimensions

Mathematics Subject Classification ID

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

Related Items (5)

Cuttings for disks and axis-aligned rectangles in three-space ⋮ On the union of cylinders in three dimensions ⋮ Lines avoiding balls in three dimensions revisited ⋮ Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications ⋮ On regular vertices of the union of planar convex objects

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On counting pairs of intersecting segments and off-line triangle range searching
• Optimal slope selection via expanders
• A deterministic view of random sampling and its use in geometry
• Fast detection of polyhedral intersection
• Partitioning arrangements of lines. II: Applications
• \(\epsilon\)-nets and simplex range queries
• Cutting hyperplane arrangements
• Randomized optimal algorithm for slope selection
• On range searching with semialgebraic sets
• Optimal slope selection via cuttings
• New applications of random sampling in computational geometry
• Reporting and counting segment intersections
• Applications of random sampling in computational geometry. II
• Reporting intersecting pairs of convex polytopes in two and three dimensions
• On a class of \(O(n^ 2)\) problems in computational geometry
• Vertical decompositions for triangles in 3-space
• Efficient algorithms for approximating polygonal chains
• Algorithms for Reporting and Counting Geometric Intersections
• Counting Circular Arc Intersections
• Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection
• An Optimal-Time Algorithm for Slope Selection
• New Lower Bounds for Convex Hull Problems in Odd Dimensions
• An optimal algorithm for intersecting line segments in the plane
• Curve-Sensitive Cuttings
• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION

This page was built for publication: Counting and representing intersections among triangles in three dimensions