|
|||||
|
|
Lower bounds for computing geometric spanners and approximate shortest paths |
|
| Authors: | Danny Z. Chen Gautam Das Michiel Smid |
| Affiliation: | a Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA b Math Sciences Department, The University of Memphis, Memphis, TN 38152, USA c Department of Computer Science, University of Magdeburg, D-39106 Magdeburg, Germany |
| Abstract: | We consider the problems of constructing geometric spanners, possibly containing Steiner points, for a set of n input points in d-dimensional space , and constructing spanners and approximate shortest paths among a collection of polygonal obstacles on the plane. The complexities of these problems are shown to be Ω(n log n) in the algebraic computation tree model. Since O(n log n)-time algorithms are known for solving these problems, our lower bounds are tight up to a constant factor. |
| Keywords: | Computational geometry Spanner graphs Shortest paths Lower bounds |
| 本文献已被 ScienceDirect 等数据库收录！ | |