论文标题
输出敏感算法用于近似发生率及其应用
Output sensitive algorithms for approximate incidences and their applications
论文作者
论文摘要
当点和对象彼此之间最多位于$ε$时，就会发生$ε$ - 点和某些几何对象（线，圆，平面，球体）之间的发生率（线，圆，平面，球体）。给定一组点和一组对象，计算它们之间的近似发生率是许多数据库和基于Web的计算机视觉和图形应用程序中的主要步骤，包括可靠的模型拟合，近似点模式匹配以及估计Epolar（立体）几何形状的基本矩阵。 在这种典型的大概发生率问题中，我们将在两个或三个维度中为$ m $ $ $ m $点，一个$ n $对象的$ s $（线，圆，飞机，球体）和一个错误参数$ε> 0 $，我们的目标是报告所有对$（p，p，s）\ times $ that that that that that that $ um laste us late late late late late late late late late laste $ um pean $ um pess $。我们为相当多的情况提供有效的输出敏感近似算法，包括平面中的点，线或圆，以及三个维度的点和平面，球，线或圆圈。这些案例中有几个出现在上述申请中。
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)\in P\times 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.
