Quick links

Computational Geometry with Imprecise Data and Arithmetic (Thesis)

Report ID:
September 1992
Download Formats:


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.

Follow us: Facebook Twitter Linkedin