Dartmouth College Computer Science Technical Report series CS home TR home TR search TR listserv By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

Path Planning Algorithms under the Link-Distance Metric
David P. Wagner
Dartmouth TR2006-585

Abstract:

The Traveling Salesman Problem and the Shortest Path Problem are famous problems in computer science which have been well studied when the objective is measured using the Euclidean distance. Here we examine these geometric problems under a different set of optimization criteria. Rather than considering the total distance traversed by a path, this thesis looks at reducing the number of times a turn is made along that path, or equivalently, at reducing the number of straight lines in the path.

Minimizing this objective value, known as the link-distance, is useful in situations where continuing in a given direction is cheap, while turning is a relatively expensive operation. Applications exist in VLSI, robotics, wireless communications, space travel, and other fields where it is desirable to reduce the number of turns.

This thesis examines rectilinear and non-rectilinear variants of the Traveling Salesman Problem under this metric. The objective of these problems is to find a path visiting a set of points which has the smallest number of bends. A 2-approximation algorithm is given for the rectilinear problem, while for the non-rectilinear problem, an O(log n)-approximation algorithm is given. The latter problem is also shown to be NP-Complete.

Next, the Rectilinear Minimum Link-Distance Problem, also known as the Minimum Bends Path Problem, is considered. Here the objective is to find a rectilinear path between two points among rectilinear obstacles which has the minimum number of bends, while avoiding passing through any of the obstacles. The problem has been well studied in two dimensions, but is relatively unexplored in higher dimensions. A main result of this thesis is an O(n^{5/2} log n) time algorithm solving this problem in three dimensions. Previously known algorithms have had worst-case running times of Omega(n^3).

This algorithm requires a data structure that supports efficient operations on pointsets within rectangular regions of the Euclidean plane. We design a new data structure, which is a variation on the segment tree, in order to support these operations.

Finally, an implementation of the data structure and of the algorithm solving the Minimum Link-Distance Problem demonstrates their experimental running times and ease of implementation.

Note: Doctoral dissertation. Co-Advisors: Robert Scot Drysdale, Clifford Stein; Thesis Committee: Amit Chakrabarti, Joseph S. B. Mitchell

PDF (1576KB)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
David P. Wagner, "Path Planning Algorithms under the Link-Distance Metric." Dartmouth Computer Science Technical Report TR2006-585, February 2006.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.