Abstract

Digital street and trail maps are typically represented by an interconnected network of path segments. These spatial networks are used in map creation, route planning, and geo-location. Consumer GPS devices have become popular as a method of collecting data for use in spatial networks. Existing methods for creating spatial networks either require extensive hand editing or use inefficient algorithms that require re-computation when adding new data to an existing network. I demonstrate a method for creating and maintaining spatial networks that allows for incremental updates without complete re-computation. I also demonstrate how spatial limits on data set growth allows networks to be updated in linear time after initial path discovery. This approach allows networks to be rapidly and accurately updated using data from consumer GPS devices.

Degree

College and Department

Physical and Mathematical Sciences; Computer Science

Rights

http://lib.byu.edu/about/copyright/