Solving Geometric Matching Problems using Interval Arithmetic Optimization

Опубликовано 6 сентября 2016, 5:06

I describe how global optimization methods based on interval arithmetic can be used for solving a variety of problems in computational geometry, including the detection of parametric geometric primitives, geometric point matching, and maximum empty rectangle problems.  These techniques can be viewed as extensions of previous work on branch-and-bound based geometric matching techniques, but they are applicable to a wider range of problems, guarantee reliable solutions even in the presence of numerical roundoff errors, and permit the use of better optimization strategies.  I discuss some applications of these techniques to geometric problems arising in document layout analysis.