/Problem1

Primary LanguageJava

Problem1

We want each teleportation to be as short as possible. Thus starting from the starting point (0, 0, 0) we teleport to the closest station each time. In the current implementation we find the closest point each time by checking all the points that we have not visited yet. This takes O(n) time where n the number of points we have to check. In the worst case, we will pass through all the points, so the final worst-case time complexity is O(n^2), where n the total number of points. We can do better by using a multidimensional BST, like a k-d tree to search for the closest point each time in O(logn) on average. Then we would have average time complexity O(nlogn). The worst-case time complexity would still be O(n^2) because the worst-case for search in a k-d tree is O(n).