Output sensitive algorithms for approximate incidences and their applications
Abstract
An ε-approximate incidence between a point and some geometric object (line, circle, plane,
sphere) occurs when the point and the object lie at distance at most ε from each other. Given a set
of points and a set of objects, computing the approximate incidences between them is a major step
in many database and web-based applications in computer vision and graphics, including robust
model fitting, approximate point pattern matching, and estimating the fundamental matrix in
epipolar (stereo) geometry.
In a typical approximate incidence problem of this sort, we are given a set P of m points
in two or three dimensions, a set S of n objects (lines, circles, planes, spheres), and an error
parameter ε > 0, and our goal is to report all pairs (p, s) ∈ P × S that lie at distance at most ε
from one another. We present efficient output-sensitive approximation algorithms for quite a few
cases, including points and lines or circles in the plane, and points and planes, spheres, lines, or
circles in three dimensions. Several of these cases arise in the applications mentioned above. Our
algorithms report all pairs at distance ≤ ε, but may also report additional pairs, all of which are
guaranteed to be at distance at most αε, for some constant α > 1. Our algorithms are based on
simple primal and dual grid decompositions and are easy to implement. We note though that (a)
the use of duality, which leads to significant improvements in the overhead cost of the algorithms,
appears to be novel for this kind of problems; (b) the correct choice of duality in some of these
problems is fairly intricate and requires some care; and (c) the correctness and performance
analysis of the algorithms (especially in the more advanced versions) is fairly non-trivial.
We analyze our algorithms and prove guaranteed upper bounds on their running time and on
the “distortion” parameter α. We also briefly describe the motivating applications, and show how
they can effectively exploit our solutions. The superior theoretical bounds on the performance
of our algorithms, and their simplicity, make them indeed ideal tools for these applications. In
a series of preliminary experimentations (not included in this abstract), we substantiate this
feeling, and show that our algorithms lead in practice to significant improved performance of the
aforementioned applications.
sphere) occurs when the point and the object lie at distance at most ε from each other. Given a set
of points and a set of objects, computing the approximate incidences between them is a major step
in many database and web-based applications in computer vision and graphics, including robust
model fitting, approximate point pattern matching, and estimating the fundamental matrix in
epipolar (stereo) geometry.
In a typical approximate incidence problem of this sort, we are given a set P of m points
in two or three dimensions, a set S of n objects (lines, circles, planes, spheres), and an error
parameter ε > 0, and our goal is to report all pairs (p, s) ∈ P × S that lie at distance at most ε
from one another. We present efficient output-sensitive approximation algorithms for quite a few
cases, including points and lines or circles in the plane, and points and planes, spheres, lines, or
circles in three dimensions. Several of these cases arise in the applications mentioned above. Our
algorithms report all pairs at distance ≤ ε, but may also report additional pairs, all of which are
guaranteed to be at distance at most αε, for some constant α > 1. Our algorithms are based on
simple primal and dual grid decompositions and are easy to implement. We note though that (a)
the use of duality, which leads to significant improvements in the overhead cost of the algorithms,
appears to be novel for this kind of problems; (b) the correct choice of duality in some of these
problems is fairly intricate and requires some care; and (c) the correctness and performance
analysis of the algorithms (especially in the more advanced versions) is fairly non-trivial.
We analyze our algorithms and prove guaranteed upper bounds on their running time and on
the “distortion” parameter α. We also briefly describe the motivating applications, and show how
they can effectively exploit our solutions. The superior theoretical bounds on the performance
of our algorithms, and their simplicity, make them indeed ideal tools for these applications. In
a series of preliminary experimentations (not included in this abstract), we substantiate this
feeling, and show that our algorithms lead in practice to significant improved performance of the
aforementioned applications.
Research Areas
