I have two nice algorithms (which I will publish when I get the chance) for which I would l like to know if there are important applications outside of those I know if in Computational Geometry. Both algorithms are on polygons. They are:
1) Visibility of objects in a n vertex simple polygon P. Consider that you want to construct a data structure that allows you to in O(1) time: a) Given two vertices or edges of P compute if there is a chord of the polygon that joins them. b) Given any two of a fixed set of points on the boundary of P compute if there is a chord of the polygon joining them. c) Given any two of a fixed set of points in the interior of P compute if there is a line segment interior to P joining them. For a) I have a data structure constructed in O(n log n) time which requires O(n log n) space. These costs are O(n) in best case and the average case is probably good. For b) and c) I have data structures constructed in O((n +k)log(n)) time which requires O((n+k) log(n)) space where k is the number of fixed points. 2) Ray shooting in a n vertex polygon: Construct a data structure that allows one to quickly shoot a ray from inside a polygon and compute the first intersection of the ray with the boundary of the polygon. There already exist 3 optimal algorithms for this problem and my solution is not optimal because the building the data structure requires O(n log n) time (optimal is O(n)) though, like the optimal algorithms, the data structure requires O(n) space and the actual ray shoot is O(log n). The advantages of my algorithm are: a) It is considerably simpler than the other algorithms. b) The constant coefficients for the complexities are lower than the optimal algorithms; thus my algorithm should be faster in practice. I expect this to be true even for the data structure construction step because the worst case O(n log n) construction time scenario is unlikely (I believe). c) The algorithm is new and quite different from the optimal solutions so there may be room for improvement. Perhaps the preprocessing can be reduced to O(n). I hasten to point out that my ray shooting algorithm is still missing a few details so my claims could in the end prove false. If you have knowledge (or ideas) of applications of these algorithms I would appreciate hearing about them. Suggestions of other groups that would be interested in my algorithms would also be appreciated. I am willing to implement these algorithms; if someone would pay me to do so of course. Thanks Ralph Boland [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---