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

This thesis presents an algorithm for computing the 3-d convex hull of

imprecise points using floating point arithmetic. The algorithm

produces a set of ''thick'' facets that contain all exact convex hulls

of the data. It is based on Quickhull and Beneath--beyond.

Parameters for the algorithm include the precision of the data and the

maximum angle between adjacent facets. This allows the user to

simplify the output and may reduce the exponential growth in output

size as dimension increases. It is the first 3-d convex hull

algorithm to work with fixed precision arithmetic. We derive a bound

for the maximum width of a facet when certain restrictions are

satisfied. The algorithm produces a data structure called a {it

locally convex box complex.} Similar to a simplicial complex, a {it

box complex} is a graded DAG of sets called {it boxes}. Each node of

the DAG is a {it face} of the box complex. A face represents a

vertex, edge, facet, or other feature. its box bounds the possible

locations of the face. A box complex is {it locally convex} when

hyperplanes define the boxes for facets, and the hyperplanes for

adjacent facets meet in a convex angle. The thesis also presents an

algorithm for point includion in box complexes and polyhedra. It

identifies a subset of the vertices. The subset has odd parity of the

point is inside and even parity if it is outside. It is the first

point--in--polyhedron algorithm to work in general dimension on

arbitrary inputs with fixed precision arithmetic. It is the first

point--in--polyhedron algorithm to work when the only geometric

information is bounding boxes.

**Links**

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

[2] ftp://ftp.cs.princeton.edu/techreports/1992/377.pdf