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.
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.
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