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

Abstract:

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.

Files:

  HijaziBreuelComputingArr.pdf

BibTex:

@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