Title: Rectilinear Path Problems Among Rectilinear Obstacles
       Revisited*

* Supported in part by the National Science Foundation under the 
  Grants CCR-8901815, and CCR-9309743, and by the Office of Naval 
  Research under the Grant N00014-93-1-0272.


Chung-Do Yang
IBM Microelectronics
EDA Physical Design
E. Fishkill Facility
Hopewell Junction, New York 12533 
e-mail: yangcd@fshvmfk1.vnet.ibm.com

D. T. Lee
Department of Electrical Engineering and Computer Science
Northwestern University
Evanston, Illinois 60208
e-mail: dtlee@eecs.nwu.edu

and 

C. K. Wong
IBM Research Division 
Thomas J. Watson Research Center
Yorktown Heights, New York 10598 
e-mail: wongck@watson.ibm.com

Abstract:

We present efficient algorithms for finding rectilinear
collision-free paths between two given points among a set of
rectilinear obstacles. Our results improve the time complexity
of previous results for finding the shortest rectilinear path, 
the minimum-bend shortest rectilinear path, the shortest 
minimum-bend rectilinear path and the minimum-cost rectilinear 
path.  For finding the shortest rectilinear path,
we use graph-theoretic approach and obtain an algorithm with
O(m\log t+ t\log^{3/2} t) running time where t is the number
of extreme edges of given obstacles, and $m$ is the number of 
obstacle edges.  Based on this result we also obtain an
O(N\log N+(m+N)\log t + (t+N)\log^2 (t+N)) running time
algorithm for computing the L_1 minimum spanning tree of given 
N terminals among rectilinear obstacles. For finding the 
minimum-bend shortest path, the shortest minimum-bend rectilinear 
path  and the minimum-cost rectilinear path, we devise a new 
dynamic-searching approach and derive algorithms that run in 
O(m\log^2m) time using O(m\log m) space or run in O(m\log^{3/2}m) 
time and space.

Keywords: rectilinear shortest path, minimum-bend path, 
	  path preserving graph, computational geometry, 
	  rectilinear obstacles

SIAM J. Computing, June 1995, pp. 457-472.