國立虎尾科技大學 |

Minimum link paths in polygons and related problems.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Minimum link paths in polygons and related problems./
Author:	Suri, Subhash.
Description:	1 online resource (233 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 49-12, Section: B.
Contained By:	Dissertations Abstracts International49-12B.
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9798206287653

Minimum link paths in polygons and related problems.
Suri, Subhash.

Minimum link paths in polygons and related problems. - 1 online resource (233 pages)

Source: Dissertations Abstracts International, Volume: 49-12, Section: B.

Thesis (Ph.D.)--The Johns Hopkins University, 1987.

Includes bibliographical references

Consider the motion of a robot in a two-dimensional Euclidean space that is bounded by a simple polygon. The robot can move only along straight-line segments and the boundary of the polygon represents an impenetrable obstacle. Suppose that it is easier for the robot to move in a straight line rather than to turn and rotate. In this thesis, we investigate problems related to paths of fewest number of turns (or minimum link paths), under the simplifying assumption that robot is a point. In particular, we present efficient algorithms for the following problems in a polygon P: (1) Find a minimum link path between two given points of P. (2) Find minimum link paths between a fixed point and all the vertices of P. (3) Preprocess P with respect to a fixed point x such that the number of edges in a minimum link path between x and a query point can be determined in logarithmic time. (4) Compute the link diameter of P (which is the maximum number of edges in any minimum link path of P). We also consider problems where the complexity of a path is measured by its Euclidean length rather than by its number of turns. In this geodesic metric, the distance between two points of the polygon is the length of the shortest Euclidean path between them. We present fast algorithms for the following problems in P: (1) Compute the geodesic diameter of P (which is the maximum distance between any two points of P). (2) Compute geodesic furthest neighbors for all the vertices of P (furthest neighbor of a point x is another point in P whose distance from x is maximum). Several open problems are discussed at the conclusion of the work.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798206287653Subjects--Topical Terms:

573171
Computer science.
Subjects--Index Terms:

RoboticsIndex Terms--Genre/Form:

554714
Electronic books.

Minimum link paths in polygons and related problems.
LDR:02837ntm a22003377 4500 001 1147151
005 20240909062230.5
006 m o d
007 cr bn ---uuuuu
008 250605s1987 xx obm 000 0 eng d
020 $a 9798206287653
035 $a (MiAaPQ)AAI8807477
035 $a AAI8807477
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Suri, Subhash. $3 1417070
245 1 0 $a Minimum link paths in polygons and related problems.
264 0 $c 1987
300 $a 1 online resource (233 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 49-12, Section: B.
500 $a Publisher info.: Dissertation/Thesis.
502 $a Thesis (Ph.D.)--The Johns Hopkins University, 1987.
504 $a Includes bibliographical references
520 $a Consider the motion of a robot in a two-dimensional Euclidean space that is bounded by a simple polygon. The robot can move only along straight-line segments and the boundary of the polygon represents an impenetrable obstacle. Suppose that it is easier for the robot to move in a straight line rather than to turn and rotate. In this thesis, we investigate problems related to paths of fewest number of turns (or minimum link paths), under the simplifying assumption that robot is a point. In particular, we present efficient algorithms for the following problems in a polygon P: (1) Find a minimum link path between two given points of P. (2) Find minimum link paths between a fixed point and all the vertices of P. (3) Preprocess P with respect to a fixed point x such that the number of edges in a minimum link path between x and a query point can be determined in logarithmic time. (4) Compute the link diameter of P (which is the maximum number of edges in any minimum link path of P). We also consider problems where the complexity of a path is measured by its Euclidean length rather than by its number of turns. In this geodesic metric, the distance between two points of the polygon is the length of the shortest Euclidean path between them. We present fast algorithms for the following problems in P: (1) Compute the geodesic diameter of P (which is the maximum distance between any two points of P). (2) Compute geodesic furthest neighbors for all the vertices of P (furthest neighbor of a point x is another point in P whose distance from x is maximum). Several open problems are discussed at the conclusion of the work.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
653 $a Robotics
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0800
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a The Johns Hopkins University. $3 1182076
773 0 $t Dissertations Abstracts International $g 49-12B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=8807477 $z click for full text (PQDT)