On May 24, 5:05 am, Albert <[email protected]> wrote:
> Hi,
>
> I'm 15 years old and I'm interested in algorithms, data structures,
> computational geometry and general coding. What sort of projects could
> I do in my spare time that fuels my interests and is something I can
> go on with? Other than competing in USACO...
>
> Thanks
> Albert
In my Ph.D. thesis is an algorithm that is quite simple yet pretty
neat
that you might enjoy implementing.
My guess is that it is at least 100 times simpler and 100 times
faster
that the previous best algorithm for polygons of practical size.
This level of improvement is possible in part because the previous
best algorithm for this problem triangulates the input polygon
and my algorithm does not!
Though I know of no applications of this algorithm the simplicity
of the problem suggests that applications are out there.
Who knows, you might be able to sell it.
The algorithm involves computing areas of polygons.
More precisely, given a polygon P, the algorithm constructs from
P a data structure with which, when given a chord C of P, the
algorithm can compute the areas of the two subpolygons of P
determined by C, say P1 and P2.
(In other words the chord C cuts the polygon P into two smaller
polygons
I call P1 and P2; that is: P = P1 union P2 union C.)
The algorithm requires linear time and space to construct the data
structure.
Then, given any input chord C, the areas of P1 and P2
are computed in constant time.
If you are interested I can email you a copy of the paper.
Actually you can find it on line by searching for my name
or the Canadian Computational Geometry Conference.
If you have problems understanding the paper I can help.
Good luck whatever you decide.
Ralph Boland
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
