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

Report ID:

TR-368-92

Authors:

Palios, Leonidas [1]

Date:

March 1992

Pages:

118

Download Formats:

[Postscript [2]]

Decomposition problems are of major importance in computational

geometry, as they allow us to express complicated objects in terms of

simpler ones, which are in general easier to process, and often lead

to more efficient algorithms. In this thesis, we present two

decomposition algorithms on three-dimensional polyhedra, one to

partition the boundary of a polyhedron of arbitrary genus into a small

number of "well-behaved" pieces, the other to partition a polyhedron

of zero genus into tetrahedra. The first algorithm decomposes the

boundary of a polyhedron of $r$ reflex angles into at most $10r - 2$

connected pieces, each of which lies on the boundary of its convex

hull. A remarkable feature of this result is that the number of these

convex-like pieces is independent of the number of vertices.

Furthermore, it is linear in $r,$ which contrasts with a quadratic

worst-case lower bound on the number of convex pieces needed to

decompose the polyhedron itself. The number of new vertices

introduced in the process is $0(n),$ and the decomposition can be

computed in $0(n + r log r)$ time. The second algorithm decomposes a

polyhedron of zero genus (a polyhedron homeomorphic to a

three-dimensional ball) that has $n$ vertices and $r$ reflex angles

into a collection of $0(n + r sup 2^)$ tetrahedra. The algorithms

runs in $0((n + r sup 2^)$ log $r)$ time and requires $0(n + r sup

2^)$ space. Up to within a constant factor, the number of tetrahedra

produced is optimal in the worst case. Discussion on an

implementation of the second algorithm in the programming language C

concludes the thesis. It involves the issues of how to carry out some

of the tasks outlined in the theoretical description, how to represent

the entities participating in the different stages of the algorithm,

and how to deal with finite precision arithmetic.

**Links**

[1] https://www.cs.princeton.edu/research/techreps/author/157

[2] https://www.cs.princeton.edu/techreports/1992/368.ps.gz