BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR2005-538
ENTRY:: May 03, 2005
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: An O(n^{5/2} log n) Algorithm for the Rectilinear Minimum Link-Distance Problem in Three Dimensions (Extended Abstract)
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Drysdale, Robert Scot
AUTHOR:: Stein, Clifford
AUTHOR:: Wagner, David P.
DATE:: May 2005
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR2005-538.pdf
ABSTRACT:: 
In this paper we consider the Rectilinear Minimum Link-Distance Problem in Three Dimensions.  The problem is well studied in two dimensions, but is relatively unexplored in higher dimensions.
We solve the problem in O(B n log n) time, where n is the number
of corners among all obstacles, and B is the size of a BSP decomposition of the space containing the obstacles.  It has been shown that
in the worst case B = Theta(n^{3/2}), giving us an overall worst case time of O(n^{5/2} log n).
Previously known algorithms have had worst-case running times of Omega(n^3).
NOTE:: 
Submitted to CCCG 2005
END:: ncstrl.dartmouthcs//TR2005-538