Output sensitive algorithms for approximate incidences and their applications

DOI10.1016/J.COMGEO.2020.101666MaRDI QIDQ827295zbMATH OpenOpenAlexFDO

Authors Dror Aiger, Haim Kaplan, Micha Sharir

Publication date 7 January 2021

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.08193, https://drops.dagstuhl.de/opus/volltexte/2017/7822/

zbMATH Keywords

data structurespattern matchingmodel fittingapproximate incidencesprimal-dual grids

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: An $epsilon$-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 $epsilon$ 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 $epsilon>0$, and our goal is to report all pairs $(p,s)inPimesS$ that lie at distance at most $epsilon$ 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.

Recommendations

• Output sensitive algorithms for approximate incidences and their applications
• scientific article; zbMATH DE number 3909744
• Output-sensitive algorithms for sumset and sparse polynomial multiplication
• scientific article; zbMATH DE number 1522945
• Output-sensitive algorithms for computing nearest-neighbour decision boundaries
• Efficient computation of tight approximations to Chernoff bounds
• Output sensitive algorithm for covering many points
• An output sensitive algorithm for discrete convex hulls
• Improved algorithms via approximations of probability distributions (extended abstract)

Cites work

• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 1305437 (Why is no real title available?)
• scientific article; zbMATH DE number 2145241 (Why is no real title available?)
• scientific article; zbMATH DE number 3289061 (Why is no real title available?)
• Approximate decision algorithms for point set congruence
• Approximate input sensitive algorithms for point pattern matching
• Approximate range searching: The absolute model
• Combinatorial and experimental methods for approximate point pattern matching
• Combinatorial geometry problems in pattern recognition
• The number of congruent simplices in a point set

Cited in

(1)

• Output sensitive algorithms for approximate incidences and their applications

This page was built for publication: Output sensitive algorithms for approximate incidences and their applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q827295)