A lower bound for computing geometric spanners

作者：Farshi Mohammad^*; Poureidi Abolfazl

来源：Computational Geometry-Theory and Applications, 2016, 53: 21-26.

DOI：10.1016/j.comgeo.2015.12.004

• Geometric network
• Spanner
• Lower bound
• Steiner spanner

It is known that the problem of computing (Steiner) spanners on a set of n points has an Omega(n logn) lower bound. However, the proof is based on an example of points on the real line. Therefore, if we assume that the points belong to the plane or higher dimensions, and moreover, they are in general position, then the lower bound example does not work. In this paper, we show that the complexity of computing geometric spanners, possibly containing Steiner points, for a set of n points in d-dimensional Euclidean space (R-d) that are in general position is Omega(n logn), in the algebraic computation tree model. To this end, we reduce the spanner construction to a variant of the closest pair problem which has an Omega(nlogn) lower bound.

• 出版日期2016-2