## Abstract

Given n pairwise disjoint non-vertical lines in 3-space, their vertical depth (i.e., above/below) relation may contain cycles. We show that the lines can be cut into O(n3/2polylogn) pieces, such that the depth relation among these pieces is a proper partial order. This bound is nearly tight in the worst case. Our proof uses a recent variant of the polynomial partitioning technique, due to Guth, and some simple tools from algebraic geometry. Our technique can be extended to eliminating all cycles in the depth relation among segments and among constant-degree algebraic arcs. Our results almost completely settle a 35-year-old open problem in computational geometry motivated by hidden-surface removal in computer graphics. We also discuss several algorithms for constructing a small set of cuts so as to eliminate all depth-relation cycles among the lines.

Original language | English (US) |
---|---|

Pages (from-to) | 725-741 |

Number of pages | 17 |

Journal | Discrete and Computational Geometry |

Volume | 59 |

Issue number | 3 |

DOIs | |

State | Published - Apr 1 2018 |

## Keywords

- Algebraic methods in combinatorial geometry
- Cycle elimination
- Depth cycles
- Depth order
- Painter’s algorithm
- Polynomial partition

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics