東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Deriving an Obstacle-Avoiding Shorte...

Hong, Insu.

Linked to FindBook

Google Book

Amazon

博客來

Deriving an Obstacle-Avoiding Shortest Path in Continuous Space: A Spatial Analytic Approach.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Deriving an Obstacle-Avoiding Shortest Path in Continuous Space: A Spatial Analytic Approach./
Author:	Hong, Insu.
Description:	151 p.
Notes:	Source: Dissertation Abstracts International, Volume: 76-09(E), Section: A.
Contained By:	Dissertation Abstracts International76-09A(E).
Subject:	Geography. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3701414
ISBN:	9781321720440

Deriving an Obstacle-Avoiding Shortest Path in Continuous Space: A Spatial Analytic Approach.
Hong, Insu.

Deriving an Obstacle-Avoiding Shortest Path in Continuous Space: A Spatial Analytic Approach. - 151 p.

Source: Dissertation Abstracts International, Volume: 76-09(E), Section: A.

Thesis (Ph.D.)--Arizona State University, 2015.

The shortest path between two locations is important for spatial analysis, location modeling, and wayfinding tasks. Depending on permissible movement and availability of data, the shortest path is either derived from a pre-defined transportation network or constructed in continuous space. However, continuous space movement adds substantial complexity to identifying the shortest path as the influence of obstacles has to be considered to avoid errors and biases in a derived path. This obstacle-avoiding shortest path in continuous space has been referred to as Euclidean shortest path (ESP), and attracted the attention of many researchers. It has been proven that constructing a graph is an effective approach to limit infinite search options associated with continuous space, reducing the problem to a finite set of potential paths. To date, various methods have been developed for ESP derivation. However, their computational efficiency is limited due to fundamental limitations in graph construction. In this research, a novel algorithm is developed for efficient identification of a graph guaranteed to contain the ESP. This new approach is referred to as the convexpath algorithm, and exploits spatial knowledge and GIS functionality to efficiently construct a graph. The convexpath algorithm utilizes the notion of a convex hull to simultaneously identify relevant obstacles and construct the graph. Additionally, a spatial filtering technique based on intermediate shortest path is enhances intelligent identification of relevant obstacles. Empirical applications show that the convexpath algorithm is able to construct a graph and derive the ESP with significantly improved efficiency compared to visibility and local visibility graph approaches. Furthermore, to boost the performance of convexpath in big data environments, a parallelization approach is proposed and applied to exploit computationally intensive spatial operations of convexpath. Multicore CPU parallelization demonstrates noticeable efficiency gain over the sequential convexpath. Finally, spatial representation and approximation issues associated with raster-based approximation of the ESP are assessed. This dissertation provides a comprehensive treatment of the ESP, and details an important approach for deriving an optimal ESP in real time.

ISBN: 9781321720440Subjects--Topical Terms:

524010
Geography.

Deriving an Obstacle-Avoiding Shortest Path in Continuous Space: A Spatial Analytic Approach.
LDR:03216nmm a2200277 4500 001 2079442
005 20170313112147.5
008 170521s2015 ||||||||||||||||| ||eng d
020 $a 9781321720440
035 $a (MiAaPQ)AAI3701414
035 $a AAI3701414
040 $a MiAaPQ $c MiAaPQ
100 1 $a Hong, Insu. $3 3195122
245 1 0 $a Deriving an Obstacle-Avoiding Shortest Path in Continuous Space: A Spatial Analytic Approach.
300 $a 151 p.
500 $a Source: Dissertation Abstracts International, Volume: 76-09(E), Section: A.
500 $a Adviser: Alan T. Murray.
502 $a Thesis (Ph.D.)--Arizona State University, 2015.
520 $a The shortest path between two locations is important for spatial analysis, location modeling, and wayfinding tasks. Depending on permissible movement and availability of data, the shortest path is either derived from a pre-defined transportation network or constructed in continuous space. However, continuous space movement adds substantial complexity to identifying the shortest path as the influence of obstacles has to be considered to avoid errors and biases in a derived path. This obstacle-avoiding shortest path in continuous space has been referred to as Euclidean shortest path (ESP), and attracted the attention of many researchers. It has been proven that constructing a graph is an effective approach to limit infinite search options associated with continuous space, reducing the problem to a finite set of potential paths. To date, various methods have been developed for ESP derivation. However, their computational efficiency is limited due to fundamental limitations in graph construction. In this research, a novel algorithm is developed for efficient identification of a graph guaranteed to contain the ESP. This new approach is referred to as the convexpath algorithm, and exploits spatial knowledge and GIS functionality to efficiently construct a graph. The convexpath algorithm utilizes the notion of a convex hull to simultaneously identify relevant obstacles and construct the graph. Additionally, a spatial filtering technique based on intermediate shortest path is enhances intelligent identification of relevant obstacles. Empirical applications show that the convexpath algorithm is able to construct a graph and derive the ESP with significantly improved efficiency compared to visibility and local visibility graph approaches. Furthermore, to boost the performance of convexpath in big data environments, a parallelization approach is proposed and applied to exploit computationally intensive spatial operations of convexpath. Multicore CPU parallelization demonstrates noticeable efficiency gain over the sequential convexpath. Finally, spatial representation and approximation issues associated with raster-based approximation of the ESP are assessed. This dissertation provides a comprehensive treatment of the ESP, and details an important approach for deriving an optimal ESP in real time.
590 $a School code: 0010.
650 4 $a Geography. $3 524010
650 4 $a Geographic information science and geodesy. $3 2122917
690 $a 0366
690 $a 0370
710 2 $a Arizona State University. $b Geography. $3 1676585
773 0 $t Dissertation Abstracts International $g 76-09A(E).
790 $a 0010
791 $a Ph.D.
792 $a 2015
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3701414