Share Email Print

Proceedings Paper

On The Complexity Of Integrating Spatial Measurements
Author(s): Thomas Dean
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

In this paper, we explore some basic issues concerning the impact of uncertainty on the complexity of map learning: assimilating sensor data to support spatial queries. The primary computational task involves consolidating a set of measurements to support queries concerning the relative position of identifiable locations. We are concerned with the complexity of providing the best possible answers to such queries. We provide a partial categorization of map learning problems according to the sorts of sensors available and the probability distributions that govern their accuracy. The objective of this exercise is to precisely define a set of computational problems and investigate the properties of algorithms that provide solutions to these problems. We show that hard problems involving uncertain measurements arise even in a single-dimensional setting. We also show that there are interesting two-dimensional map learning problems that can be solved in polynomial time. By considering basic time/space tradeoffs, we provide some insight into exactly what makes map learning hard, and how various sensors might be employed to circumvent combinatorial problems.

Paper Details

Date Published: 5 January 1989
PDF: 8 pages
Proc. SPIE 1003, Sensor Fusion: Spatial Reasoning and Scene Interpretation, (5 January 1989); doi: 10.1117/12.948950
Show Author Affiliations
Thomas Dean, Brown University (United States)

Published in SPIE Proceedings Vol. 1003:
Sensor Fusion: Spatial Reasoning and Scene Interpretation
Paul S. Schenker, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?