Computing Arrangements using Subdivision and Interval Arithmetic

Younis Hijazi, Thomas Breuel
Proceedings of the Sixth International Conference on Curves and Surfaces, Computer Aided Geometric Design, Avignon, France, 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.




@inproceedings{ HIJA2007,
	Title = {Computing Arrangements using Subdivision and Interval Arithmetic},
	Author = {Younis Hijazi and Thomas Breuel},
	BookTitle = {Proceedings of the Sixth International Conference on Curves and Surfaces},
	Year = {2007},
	Series = {Computer Aided Geometric Design},
	Publisher = {Elsevier}

Last modified:: 30.08.2016