Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-288-90

Authors:

Chazelle, Bernard [1] / Edelsbrunner, Herbert [2] / Guibas, Leonidas [3] / Pollack, Richard [4] / Seidel, Raimund [5] / Sharir, Micha [6] / Snoeyink, Jack [7]

Date:

September 1990

Pages:

19

Download Formats:

[PDF [8]]

A number of rendering algorithms in computer graphics sort three-dimensional objects by depth and assume that there is no cycle that makes the sorting impossible. One way to resolve the problem caused by cycles is to cut the objects into smaller pieces. In this paper we address the problem of estimating

how many such cuts are always sufficient. We also consider a few related algorithmic and combinatorial geometry problems. For example, we demonstrate that n lines in space can be sorted in randomized expected time O(n4/3+epsilon), provided they define no cycle. We also prove an O(n7/4) upper bound on the number of points in space so that there are n lines with the property that for each point there are at least three non-coplanar lines that contain it.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/283

[2] http://www.cs.princeton.edu/research/techreps/author/404

[3] http://www.cs.princeton.edu/research/techreps/author/417

[4] http://www.cs.princeton.edu/research/techreps/author/713

[5] http://www.cs.princeton.edu/research/techreps/author/718

[6] http://www.cs.princeton.edu/research/techreps/author/461

[7] http://www.cs.princeton.edu/research/techreps/author/466

[8] ftp://ftp.cs.princeton.edu/techreports/1990/288.pdf