An O(n 5=2 log n) Algorithm for the Rectilinear Minimum Link-Distance Problem in Three Dimensions (Extended Abstract) (Dartmouth Computer Science Technical Report TR2005-538)
Robert L. Scot, Drysdale Cliord, David P. Wagner · 2005
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( n log n) time, where n is the number of corners among all obstacles, and is the size of a BSP decomposition of the space containing the obstacles. It has been shown that in the worst case = ( 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 ( n 3 ).