Investigating Euclidean Problems under the Bend Metric
Scot Drysdale, Cliff Stein, Neal Young, David Wagner

Overview.

Our research concentrates on solving combinatorial problems in the Euclidean plane, but instead of using the classical metric of minimizing distance, we look at the possibility that it may be desirable to optimize other variables. In particular, we are interested in minmizing the amount of turning done instead of, or in addition to minimizing distance.

Problems studied

We have studied several problems under the bends metric. Our research has revealed that the minimization of bends is often a very different problem than that of minimizing distance.

Minimum Bends Travelling Salesman

We introduced the Minimum Bends Travelling Salesman Problem. This is identical to the Euclidean Travelling Salesman Problem, except that we wish to minimize the number of times which the Euclidean Traveller must make a turn. We have shown that this problem is NP-Complete, and have found an O(log n) approximation algorithm for it. [cite ipco01]

This is a variation on the Angular Metric Travelling Salesman Problem, introduced by Aggarwal, Coppersmith, Khanna, Motwani, and Schieber. Their problem attempts to minimized the total angle turned, whereas our problem attempts to minimize the number of times a turn is taken. They have shown their problem to be NP-Complete, and have given a O(log n) approximation algorithm. [cite soda97]

We also introduced a related problem, the Rectilinear Minimum Bends Traveling Salesman Problem. In this variant of the problem we only allow the salesman to travel horizontally or vertically. We have found a 2-approximation algorithm for this problem. We have also shown that if no two destination points share an x-coordinate or a y-coordinate, that this problem can be approximated to within two additional bends beyond the optimal number. [cite ipco01]

Minimum Bends Path with obstacles

This problem attempts to find a path among obstacles between two points, which minimizes the number of bends alond the path. Rectilinear variants of this problem have been previously studied by Lee, Yang, and Wong. They have found algorithms which solve this problem in O(n log n) time. [cite isaac96]

We have been looking at this problem in higher dimensions. Our preliminary results indicate that we can find a O(D n^2 log n) algorithm in higher dimensions. In particular this would be a substantial improvement over previously published results in three dimensions by Fitch, Butler, and Rus. [cite iros01]

Minimum Bends Spanning Tree with obstacles

This problem attempts to minimize the number of bends in a tree among obstacles connecting multiple points. The rectilinear problem is directly applicable to wire routing in VLSI. We have begun to start work on this and consider it a possible direction for our future research.

References

SW01 Clifford Stein, David P. Wagner. Approximation Algorithms for the Minimum Bends Travelling Salesman Problem. Integer Programming and Combinatorial Optimization, 2001.

ABDFMS01 Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Joseph S. B. Mitchell, and Saurabh Sethia. Optimal Covering Tours with Turn Costs. Symposium on Discrete Algorithms, 2001.

FBR01 Robert Fitch, Zach Butler, Daniela Rus. 3D Rectilinear Motion Planning with Minimum Bend Paths. International Conference on Intelligent Robots and Systems, 2001.

LYW96 D.T. Lee, C.D. Yang, C.K. Wong. Rectilinear Paths among Rectilinear Obstacles. International Symposium on Algorithms and Computation, 1996.

ACKMS97 Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber. The Angular-Metric Traveling Salesman Problem. Symposium on Discrete Algorithms, 1997.

A96 Sanjeev Arora. Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems Journal of the ACM, 1996.

F96 Uriel Feige. A threshold of ln n for approximating set cover. Symposium on the Theory of Computing, 1996.