Eliminating depth cycles among triangles in three dimensions

DOI10.1007/s00454-020-00221-zzbMath1462.68202arXiv1607.06136MaRDI QIDQ2207590

Boris Aronov, Edward Y. Miller, Micha Sharir

Publication date: 23 October 2020

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

Full work available at URL: https://arxiv.org/abs/1607.06136

zbMATH Keywords

polynomial partitioning; cycle elimination; algebraic methods in combinatorial geometry; depth cycles; depth order; Painter's algorithm

Mathematics Subject Classification ID

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

52C35: Arrangements of points, flats, hyperplanes (aspects of discrete geometry)

14Q20: Effectivity, complexity and computational aspects of algebraic geometry

52C45: Combinatorial complexity of geometric structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Erdős distinct distances problem in the plane
• Efficient binary space partitions for hidden-surface removal and solid modeling
• Counting and cutting cycles of lines and rods in space
• Ray shooting, depth orders and hidden surface removal
• Linear size binary space partitions for uncluttered scenes
• Almost tight bounds for eliminating depth cycles in three dimensions
• Removing depth-order cycles among triangles: an algorithm generating triangular fragments
• Binary Space Partitions for Axis-Aligned Fat Rectangles
• Computing and Verifying Depth Orders
• Eliminating Depth Cycles among Triangles in Three Dimensions
• Binary Space Partitions for Fat Rectangles
• Constructive Polynomial Partitioning for Algebraic Curves in ℝ³ with Applications
• Polynomial partitioning for a set of varieties
• Lower Bounds for Approximation by Nonlinear Manifolds
• Cutting triangular cycles of lines in space
• Online point location in planar arrangements and its applications