東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Fast methods for computing all-to-al...

Chester, Elizabeth Jenny.

Linked to FindBook

Google Book

Amazon

博客來

Fast methods for computing all-to-all geodesic paths for the Eikonal equation.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Fast methods for computing all-to-all geodesic paths for the Eikonal equation./
Author:	Chester, Elizabeth Jenny.
Description:	127 p.
Notes:	Adviser: James Sethian.
Contained By:	Dissertation Abstracts International69-03B.
Subject:	Geodesy. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3306098
ISBN:	9780549528043

Fast methods for computing all-to-all geodesic paths for the Eikonal equation.
Chester, Elizabeth Jenny.

Fast methods for computing all-to-all geodesic paths for the Eikonal equation. - 127 p.

Adviser: James Sethian.

Thesis (Ph.D.)--University of California, Berkeley, 2007.

This thesis presents the Geodesic Path-Switching algorithm, a method for solving an all-to-all shortest path problem in a continuous region. Given a domain and a metric, the goal is to compute the shortest geodesic path between a collection of points given in the domain. The metric can be thought of as a cost function defined at every point in space, and the actual paths and cost must be computed. For every pair of starting and end points, the path corresponds to the solution of the Eikonal equation for a wave starting at the source and ending at the end point.

ISBN: 9780549528043Subjects--Topical Terms:

550741
Geodesy.

Fast methods for computing all-to-all geodesic paths for the Eikonal equation.
LDR:04541nam 2200361 a 45 001 939977
005 20110517
008 110517s2007 ||||||||||||||||| ||eng d
020 $a 9780549528043
035 $a (UMI)AAI3306098
035 $a AAI3306098
040 $a UMI $c UMI
100 1 $a Chester, Elizabeth Jenny. $3 1264084
245 1 0 $a Fast methods for computing all-to-all geodesic paths for the Eikonal equation.
300 $a 127 p.
500 $a Adviser: James Sethian.
500 $a Source: Dissertation Abstracts International, Volume: 69-03, Section: B, page: 1681.
502 $a Thesis (Ph.D.)--University of California, Berkeley, 2007.
520 $a This thesis presents the Geodesic Path-Switching algorithm, a method for solving an all-to-all shortest path problem in a continuous region. Given a domain and a metric, the goal is to compute the shortest geodesic path between a collection of points given in the domain. The metric can be thought of as a cost function defined at every point in space, and the actual paths and cost must be computed. For every pair of starting and end points, the path corresponds to the solution of the Eikonal equation for a wave starting at the source and ending at the end point.
520 $a The algorithm presented is a dynamic programming method. At its core, it exploits methods borrowed from discrete graph theory to compute the solution to our continuous problem. We find shortest paths in subproblems, then use those paths as segments of a different shortest path. This method can be used to find path lengths for the shortest path between multiple pairs of endpoints. The algorithm also produces the position of an approximate path.
520 $a The path length is the time it takes to traverse the path, according to a known, position dependent speed function. We place a simple rectangular mesh on the region, which provides a graph-like setting for the problem. We apply concepts of methods used to solve the all-to-all shortest path problem on a graph to our continuous setting.
520 $a Floyd's algorithm is a method for solving the shortest path problem on a graph. It compares currently known paths to new paths made by joining two paths, one each from our original endpoints to a third node. Upon completion of the algorithm, we have shortest path lengths and the actual shortest paths for every pair of nodes in the graph.
520 $a In the continuous setting, mesh points play a similar role as the nodes in the graph setting. They describe endpoints of paths, and they determine regions through which we describe potential new shortest paths. The cell boundaries describe edges. A significant difference between the graph problem and the continuous problem is the potential paths whose length we seek to minimize. On a graph, paths may be made only from existing edges on the graph. In the continuous region, paths may pass through any point in the region.
520 $a We present a method for minimizing patty that intersect some small subregion at some point. We construct contours of known path lengths to determine the length of shortest paths made by joining together two paths at some point within that subregion. The dynamic programming principle of Floyd's algorithm motivates our method for comparing paths in order to find the shortest path. We use the upwind update procedure from the Fast Marching method to calculate path lengths for a small region.
520 $a The Geodesic Path-Switching algorithm produces shortest path lengths for every pair of mesh points. The algorithm may be slightly modified as to record a predecessor edge for each pair of mesh points. This is the last edge visited prior to reaching the destination node of the shortest path. Upon completion of the algorithm, we use this information to work backward along the series of edges through which the shortest path passes.
520 $a At every stage in the algorithm, we have a current shortest path for each pair of mesh points. This is the shortest path we have located to that point in the algorithm. When we find a shorter path, we adopt this as our new shortest path. As a result, there are paths present at each step of Geodesic Path-Switching method. This provides alternate paths for problems which allow suboptimal paths.
590 $a School code: 0028.
650 4 $a Geodesy. $3 550741
650 4 $a Mathematics. $3 515831
690 $a 0370
690 $a 0405
710 2 $a University of California, Berkeley. $3 687832
773 0 $t Dissertation Abstracts International $g 69-03B.
790 $a 0028
790 1 0 $a Sethian, James, $e advisor
791 $a Ph.D.
792 $a 2007
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3306098