Exact cell decomposition on base map features for optimal path finding

Shuk Ching Lilian Cheng, M. Y.F. Tang, I. K.L. Cheung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)


Path-finding problems have attracted widespread research interest in GIS-T. Previous research has largely been conducted on developing shortest path algorithms in GIS. The conventional approach is to adopt the arc-node network model, which allows only users with expert knowledge to generate measurements such as optimal paths from a map. However, the generation and maintenance of a centreline network are difficult and tedious because these are not natural on-ground features but imaginary lines on a map. To remedy the situation, a revolutionary approach has been suggested that path-finding method is independent of extra arc-node data creations by end-users. By using the cell-decomposition method borrowed from motion planning of a robot, general map users may obtain an optimal path by just identifying familiarized symbols/outlines from a digital topographic map without resorting to generating an extra set of centrelines.
Original languageEnglish
Pages (from-to)175-185
Number of pages11
JournalInternational Journal of Geographical Information Science
Issue number2
Publication statusPublished - 1 Jan 2007

ASJC Scopus subject areas

  • Geography, Planning and Development
  • Information Systems
  • Library and Information Sciences


Dive into the research topics of 'Exact cell decomposition on base map features for optimal path finding'. Together they form a unique fingerprint.

Cite this