Computing Arrangements using Subdivision and Interval Arithmetic

Younis Hijazi, Thomas Breuel

In: Proceedings of the Sixth International Conference on Curves and Surfaces. International Conference on Curves and Surfaces 6th June 29-July 5 Avignon France Computer Aided Geometric Design Elsevier 2007.


Computing arrangements of curves is a fundamental and challenging problem in computational geometry, with many practical applications in a wide range of fields, including robot motion planning and computer vision. This paper describes a method for computing arrangements of implicitly defined curves. Our method for computing arrangements is an adaptation of methods successfully used for the exploration of large, higher dimensional, non-algebraic arrangements in computer vision. While broadly similar to subdivision methods in computational geometry, its design and philosophy are different; for example, it replaces exact computations by subdivision and interval arithmetic computations and prefers data-independent subdivisions. It can be used (and is usually used in practice) to compute well-defined approximations to arrangements, but can also yield exact answers for specific problem classes.

HijaziBreuelComputingArr.pdf (pdf, 325 KB )

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence