| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Output sensitive algorithms for approximate incidences and their applications | Dror Aiger
; Haim Kaplan
; Micha Sharir
; | Date: |
17 May 2020 | 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)in P imes S$ 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. | Source: | arXiv, 2005.8193 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |