Publikation
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.
Zusammenfassung
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.