I'm trying to wrap my head around this problem. I compute a visibility graph in order for a robot to move around, and an obvious application in this graph is to find a shortest path. Now finding the start and end of this path is not difficult, but to the best of my knowledge the shortest-path algorithm does not run in O(n log n) time which I have been told is possible with "appropriate preprocesing". Is there some feature about visibilty graphs that makes this possible, that anyone can outline?
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---