Colloquium Speaker

Speaker: 
Robert Scot Drysdale
Topic: 
The Rectilinear Minimum Bends Path Problem
Date: Tuesday, April 26, 2005
Time: 11:00AM
Place: Gould-Simpson, Room 701
Refreshments will be served in the 7th floor lobby of Gould-Simpson at 10:45 AM

Abstract

In this talk we consider the Rectilinear Minimum Bends Path Problem (also known as the Minimum Link-Distance Problem) among rectilinear obstacles in three dimensions. The problem is well studied in two dimensions, but is relatively unexplored in higher dimensions. We give an algorithm which solves the three dimensional problem in worst-case O(b nlog 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 = O(n1.5), giving us an overall worst case time of O(n2.5 log n). However in many practical circumstances we will have b = O(n). Previously known algorithms have a worst-case running time of O(n3).