liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Using connectivity graphs to support map-related reasoning
Linköping University, Department of Computer and Information Science. Linköping University, The Institute of Technology.
1991 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

This thesis describes how connectivity graphs can be used to support automated as well as human reasoning about certain map-related problems. Here, the term "map" intends to denote the representation of any two-dimensional, planar surface which can be partitioned into regions of free vs. obstructed space. This thesis presents two methods for solving shortest path problems within such maps. One approach involves the use of heuristic rules of inference, while the other is purely algorithmic. Both approaches employ A* search over a connectivity graph -- a graph abstracted from the map’s 2-D surface information. This work also describes how the algorithmic framework has been extended in order to supply users with graphical replies to two other map- related queries, namely visibility and localization. The technique described to solve these latter two queries is unusual in that the graphical responses provided by this system are obtained through a process of synthetic construction. This thesis finally offers outlines of proofs regarding the computational complexity of all algorithmic methods employed.

Place, publisher, year, edition, pages
Linköping: Univ. , 1991. , p. 81
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 260
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-160723Local ID: LiU-Tek-Lic-1990:60ISBN: 9178707390 (print)OAI: oai:DiVA.org:liu-160723DiVA, id: diva2:1357717
Available from: 2019-10-04 Created: 2019-10-04 Last updated: 2020-01-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Search in DiVA

By author/editor
Holmes, Peter D.
By organisation
Department of Computer and Information ScienceThe Institute of Technology
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 4 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf