On computing the shortest path in a multiply-connected domain having curved boundaries
This submission is a communication related to a recently published article in Computer-Aided Design journal, titled Shortest path in a multiply-connected domain having curved boundaries. We point out an error in estimating the time complexity of the algorithm proposed in that paper, using a simple example. We also illustrate, with a different example, that an ostensibly time-saving scheme used by that algorithm, called exterior region elimination, cannot be applied in general to derive the correct shortest interior path. Finally, we propose an alternate algorithm that solves the same problem with an improved worst-case running time.
shortest path curve obstacles multiply-connected curves visibility graph freeform curves