and that polygons are convex? 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 -~----------~----~----~----~------~----~------~--~---
