Computational Geometry with Imprecise Data and Arithmetic (Thesis)
Report ID: TR-377-92Author: Barber, C. Bradford
Date: 1992-10-00
Pages: 204
Download Formats: |PDF|
Abstract:
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.