论文标题
关于圆圈和相关问题的平面布置的丰富镜头
On rich lenses in planar arrangements of circles and related problems
论文作者
论文摘要
我们表明，在飞机上的$ n $ circles的安排中，成对的非重叠$ k $ -rich镜头（镜头至少由$ k $ circle形成）为$ o \ left（\ frac {n^{3/2} {3/2} {3/2} \ log {（n/k^3）}}} \ right）$，以及这样一个家庭镜头的学位总和（其中镜头的程度是形成它的圆的数量）为$ o \ left（\ frac {n^{3/2} \ log {（n/k^3）}}}}给出了这些界限的两个独立证明，每个证明本身都很有趣（所以我们相信）。然后，我们表明这些界限导致了Agarwal等人的已知界限。 （JACM 2004）以及Marcus and Tardos（JCTA 2006）关于飞机上的点圈发病率的数量。还考虑了更通用代数曲线和其他一些相关问题的家庭的扩展。
We show that the maximum number of pairwise non-overlapping $k$-rich lenses (lenses formed by at least $k$ circles) in an arrangement of $n$ circles in the plane is $O\left(\frac{n^{3/2}\log{(n/k^3)}}{k^{5/2}} + \frac{n}{k} \right)$, and the sum of the degrees of the lenses of such a family (where the degree of a lens is the number of circles that form it) is $O\left(\frac{n^{3/2}\log{(n/k^3)}}{k^{3/2}} + n\right)$. Two independent proofs of these bounds are given, each interesting in its own right (so we believe). We then show that these bounds lead to the known bound of Agarwal et al. (JACM 2004) and Marcus and Tardos (JCTA 2006) on the number of point-circle incidences in the plane. Extensions to families of more general algebraic curves and some other related problems are also considered.
