Personal tools
You are here: Home Projects In-house Projects Controlled Perturbation of Circles
« November 2017 »
November
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
2627282930
Log in


Forgot your password?
 

Controlled Perturbation for Arrangements of Circles

[Circle Arrangement]

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 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
    International Journal of Computational Geometry and Applications, 14(4-5): 277-310, 2004, Special issue papers from SoCG 2003 [link][bibtex]
    A preliminary version appeared in Proceedings of the 19th ACM Symposium on Computational Geometry (SoCG), 264-273 San Diego, 2003 [link][bibtex]
  • Eran Leiserowitz
    M.Sc. thesis [pdf] [bibtex]

Contact

Eran Leiserowitz http://www.cs.tau.ac.il/~leiserow leiserow@post.tau.ac.il
Dan Halperin http://acg.cs.tau.ac.il/danhalperin halperin@post.tau.ac.il
Document Actions