An improved upper bound for the size of the sphere of influence graph

Dan Ismailescu, Sung Hoon Kim, Taeyang David Park

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 neig…