An O(n^{5/2} log n) Algorithm for the Rectilinear Minimum Link-Distance Problem in Three Dimensions (Extended Abstract)

Dartmouth Technical Report TR2005-538

	Robert Scot Drysdale
	Clifford Stein
	David P. Wagner

Date: May 2005

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR2005-538.pdf> (116KB)

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