Almost tight bounds for eliminating depth cycles in three dimensions

DOI10.1007/s00454-017-9920-9zbMath1390.68703arXiv1512.00358MaRDI QIDQ1745206

Boris Aronov, Micha Sharir

Publication date: 20 April 2018

Published in: Discrete \& Computational Geometry, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

computational geometry; polynomial partitioning; cycle elimination; lines in space; algebraic methods in combinatorial geometry; depth cycles; depth order; Painter's algorithm; polynomial partition; 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