论文标题
改进的影响力图的上限
An improved upper bound for the size of the sphere of influence graph
论文作者
论文摘要
让$ v $是飞机上$ n $点的一组。对于V $中的每个$ x \，令$ b_x $为封闭的圆盘，以$ x $为中心，半径等于从$ x $到其最接近的邻居的距离。 $ v $上的{\ it封闭范围的影响图}定义为无方向的图，其中$ x $和$ y $在且仅当$ b_x $和$ b_y $具有非空交点时。 众所周知，每一个$ n $ vertex封闭范围的影响力最多都具有$ CN $边缘，对于某些绝对正常的$ c $。第一个结果是由Avis和Horton在1985年获得的，后者提供了$ C = 29 $的值。他们的结果已被几位作者改进：Bateman和Erdős（C = 18），Michael和Quint（C = 17.5）和SOSS（C = 15）。 在本文中，我们证明可以服用$ C = 14.5 $。
Let $V$ be a set of $n$ points in the plane. For each $x\in V$, let $B_x$ be the closed circular disk centered at $x$ with radius equal to the distance from $x$ to its closest neighbor. The {\it closed sphere of influence graph} on $V$ is defined as the undirected graph where $x$ and $y$ are adjacent if and only if the $B_x$ and $B_y$ have nonempty intersection. It is known that every $n$-vertex closed sphere of influence graph has at most $cn$ edges, for some absolute positive constant $c$. The first result was obtained in 1985 by Avis and Horton who provided the value $c=29$. Their result was successively improved by several authors: Bateman and Erdős (c=18), Michael and Quint (c=17.5), and Soss (c=15). In this paper we prove that one can take $c=14.5$.
