Counting and representing intersections among triangles in three dimensions

DOI10.1016/J.COMGEO.2005.02.003MaRDI QIDQ2571213zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Counting and representing intersections among triangles in three dimensions
• On a triangle counting problem
• On counting pairs of intersecting segments and off-line triangle range searching
• Counting triangle crossings and halving planes
• On ray shooting for triangles in 3-space and related problems

Cites work

• scientific article; zbMATH DE number 49092 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION
• A deterministic view of random sampling and its use in geometry
• Algorithms for Reporting and Counting Geometric Intersections
• An Optimal-Time Algorithm for Slope Selection
• An optimal algorithm for intersecting line segments in the plane
• Applications of random sampling in computational geometry. II
• Counting Circular Arc Intersections
• Curve-Sensitive Cuttings
• Cutting hyperplane arrangements
• Efficient algorithms for approximating polygonal chains
• Fast detection of polyhedral intersection
• New Lower Bounds for Convex Hull Problems in Odd Dimensions
• New applications of random sampling in computational geometry
• On a class of \(O(n^ 2)\) problems in computational geometry
• On counting pairs of intersecting segments and off-line triangle range searching
• On range searching with semialgebraic sets
• Optimal slope selection via cuttings
• Optimal slope selection via expanders
• Partitioning arrangements of lines. II: Applications
• Randomized optimal algorithm for slope selection
• Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection
• Reporting and counting segment intersections
• Reporting intersecting pairs of convex polytopes in two and three dimensions
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Vertical decompositions for triangles in 3-space
• -nets and simplex range queries

Cited in

(6)

• Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
• Lines avoiding balls in three dimensions revisited
• Cuttings for disks and axis-aligned rectangles in three-space
• On regular vertices of the union of planar convex objects
• Counting and representing intersections among triangles in three dimensions
• On the union of cylinders in three dimensions

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

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