|
Title:
Controlled Perturbation for Arrangements of Circles
Author(s):
Dan Halperin, Eran Leiserowitz
Main site:
Tel-Aviv
Restrictions:
Public
Abstract:
Given a collection C of circles in the plane, we wish to construct the arrangement
A(C) (namely the subdivision of the plane into vertices, edges and faces induced
by C) using floating point arithmetic. We present an efficient scheme, controlled
perturbation, that perturbs the circles in C slightly to form a collection C', so that
all the predicates that arise in the construction of A(C') are computed accurately
and A(C') is degeneracy free.
We introduced controlled perturbation several years ago, and already applied it
to certain types of arrangements. The major contribution of the current work is the
derivation of a good (small) resolution bound, that is, a bound on the minimum
separation of features of the arrangement that is required to guarantee that the
predicates involved in the construction can be safely computed with the given (lim-
ited) precision arithmetic. A smaller resolution bound leads to smaller perturbation
of the original input.
We present the scheme, describe how the resolution bound is determined and
how it effects the perturbation magnitude. We implemented the perturbation
scheme and the construction of the arrangement and we report on experimental
results.
Download this deliverable.
|
