An O(n5/2logn) algorithm for the Rectilinear Minimum Link-Distance Problem in three dimensions

In this paper we consider the Rectilinear Minimum Link Path Problem among rectilinear obstacles in three dimensions. The problem is well studied in two dimensions, but is relatively unexplored in higher dimensions. We solve the problem in O(βnlogn) time, where n is the number of corners among all obstacles, and β is the size of a binary space partition (BSP) decomposition of the space containing the obstacles. There exist methods to find a BSP where in the worst-case β=Θ(n3/2), giving us an overall worst-case time of O(n5/2logn). Previously known algorithms have had worst-case running times of Ω(n3).