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 presented 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 (limited) 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.
Links
Eran Leiserowitz and
Dan Halperin Controlled Perturbation for Arrangements of Circles To appear in International Journal of Computational Geometry and Applications,
Special issue, papers from SoCG 2003.
A preliminary version appeared in Proc. 19th ACM Symposium on Computational Geometry, SoCG 2003,
San Diego, 264-273.
[BibTex,
pdf full version]
![[Circle Arrangement]](../images/circ_arr.gif)
![[Projects Page]](../images/icons/projects.gif){kind=icon}
![[Top]](../images/icons/top.gif){kind=icon}
