%T An O(n^{5/2} log n) Algorithm for the Rectilinear Minimum Link-Distance Problem in Three Dimensions (Extended Abstract)
%A Robert Scot Drysdale
%A Clifford Stein
%A David P. Wagner
%R Technical Report TR2005-538
%I Dartmouth College, Computer Science
%C Hanover, NH
%D May 2005
%U http://www.cs.dartmouth.edu/reports/TR2005-538.pdf
%X
 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).
%Z
 Submitted to CCCG 2005