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
-~----------~----~----~----~------~----~------~--~---
