On May 28, 8:27 am, Miroslav Balaz <gpsla...@googlemail.com> wrote:
> and that polygons are convex?
No, the polygon need not be convex,
though my algorithm is based upon an algorithm
that only works for convex polygons.
In fact the polygon need not be simple though
what you mean by area and chord for
non simple polygons needs to be defined.
Of particular interest are overlapping polygons.
Overlapping polygons can have multiple horizontal trapezoidizations.
In my paper I show that the sum of the areas of the trapezoids
of each trapezoidization is the same;
an intuitive result perhaps but it's not at all clear how to prove it.
My point in all this though is that the algorithm is simple enough
for a 15 year old interested in computational geometry to
implement.
Ralph Boland
>
> 2009/5/25 Ralph Boland <rpbol...@gmail.com>
>
>
>
> > On May 24, 5:05 am, Albert <albert.xtheunkno...@gmail.com> 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 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
-~----------~----~----~----~------~----~------~--~---
