Output sensitive algorithms for approximate incidences and their applications

Dror Aiger, Haim Kaplan, Micha Sharir

Abstract

In computational geometry and computer vision, identifying approximate incidences—where points and geometric objects are within a small distance $\epsilon$—is a critical yet computationally expensive task. Traditional grid-based methods often suffer from high overhead as $\epsilon$ decreases, while exact theoretical algorithms are frequently too complex for practical implementation. This paper presents a suite of output-sensitive, primal-dual grid-based algorithms that bridge this gap. By combining spatial partitioning with geometric duality, these algorithms achieve significant speedups for point-line, point-plane, and other incidence problems. Experimental results on synthetic and real-world datasets demonstrate that the proposed methods outperform naive grid searches, particularly as dataset size increases.

Introduction

Detecting when a point is "close enough" to a geometric object is a fundamental operation in tasks such as RANSAC model fitting, point pattern matching, and stereo vision. In practice, sensor noise and numerical precision issues necessitate searching for approximate incidences rather than exact ones. The challenge lies in developing algorithms that are both theoretically efficient and practically implementable.

Methodology: Primal-Dual Grid Decomposition

The core innovation of this work is a two-stage primal-dual grid decomposition designed to minimize the overhead associated with small $\epsilon$ values.

Primal Stage

The algorithm begins by partitioning the input points into a coarse primal grid. Unlike naive approaches that use a grid size proportional to $\epsilon$, this coarse grid uses a much larger cell size $\delta_1$. This initial step reduces the number of grid cells an object (like a line) must intersect, thereby decreasing the initial processing overhead.

Figure 1: Primal grid partitioning where points are grouped into coarse cells of size $\delta_1$.

Dual Stage and Refinement

For each cell in the primal grid, the problem is transformed into a dual space. In this space, the roles of points and objects are often inverted (e.g., points become lines and lines become points). A second grid is then constructed in the dual space to further prune the search space.

A key aspect of this approach is the use of vertical distance as a proxy for Euclidean distance. For lines with a bounded slope (e.g., $\le \pi/4$), the vertical distance $dist_v(p, \ell)$ provides a reliable approximation of the true distance $dist(p, \ell)$, as shown in Figure 2. This geometric property allows the algorithm to maintain efficiency while guaranteeing that all true $\epsilon$-incidences are captured, albeit with some "false positives" that are easily filtered in a final pass.

Figure 2: Geometric relationship between Euclidean distance and vertical distance for lines with bounded slope.

Results and Discussion

The algorithms were evaluated against synthetic data and real-world edge-point data from high-resolution imagery.

Performance and Scaling

The primal-dual approach demonstrated a clear theoretical and practical advantage. For 2D point-line incidences, the overhead was reduced from $O(n/\epsilon)$ in naive grids to $O(\sqrt{mn/\epsilon})$. Experimental results confirmed that as the number of points and lines $n$ increases, the performance gap between the proposed "Efficient-duality" algorithm and naive grid methods widens significantly.

Approximation Quality

While the algorithm is an approximation scheme that may return pairs up to a constant factor $\alpha\epsilon$ away (where $\alpha$ is typically between 5 and 8), empirical tests showed that the number of "extra" pairs is small. These false positives grow only linearly with $\epsilon$ and do not significantly impact the overall runtime after the final filtering step.

Conclusion

By leveraging geometric duality within a grid-based framework, this work provides a practical solution for large-scale approximate incidence problems. The resulting algorithms are simple to implement, output-sensitive, and offer superior scaling compared to traditional grid-based methods. Future work includes extending these dualities to higher-dimensional manifolds and further optimizing parameter selection for black-box applications.

Summary updated

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 problem-dependent constant α > 1 . Our algorithms are based on simple primal and dual grid decompositions and are easy to implement. We note 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 α.
BibTeX
@article{aiger2020output,
  author = {Dror Aiger and Haim Kaplan and Micha Sharir},
  title = {{Output sensitive algorithms for approximate incidences and their applications}},
  journal = {Comput. Geom.},
  year = {2020},
  doi = {10.1016/j.comgeo.2020.101666},
}
Figure