THE SPATIAL SEARCH PROBLEM - STRUCTURE AND COMPLEXITY

Authors
MAIER G
Citation
G. Maier, THE SPATIAL SEARCH PROBLEM - STRUCTURE AND COMPLEXITY, Geographical analysis, 25(3), 1993, pp. 242-251
Citations number
20
Categorie Soggetti
Geografhy
Journal title
Geographical analysis → ACNP
ISSN journal
00167363
Volume
25
Issue
3
Year of publication
1993
Pages
242 - 251
Database
ISI
SICI code
0016-7363(1993)25:3<242:TSSP-S>2.0.ZU;2-X
Abstract
The paper discusses structure and complexity of the spatial search pro blem. From a set of assumptions it derives a rather general version of the spatial search problem and investigates some of its fundamental p roperties. Most importantly, the paper shows that the decision problem corresponding to the spatial search problem in this general version i s NP-complete.