Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-04-09 19:20:10

Andriy Sydorchuk wrote:
> Well this is general approach used to solve problem with sweepline
> algorithm. What I am asking about are algorithm details.
> For voronoi diagram there is exact prototype of algorithm (as example
> "An Efficient Implementation of Fortune's Plane-Sweep Algorithm for
> Voronoi Diagrams" KennyWong, Hausi A. Muller, page 18). This
> prototype is definitely not the same for medial axis and straight
> skeleton problems. If it is common approach to solve this problems
> with sweepline, so there should be some articles and theory about
> that, but I haven't found them. Maybe I am 
> expected to develop this prototype on my own, am I?

There are papers that you can read.  At a certain point you may need take a leap of intuition from the description of the algorithm to an understanding of the algorithm, and a well written paper should at least get you to the point where you are capable of making that leap.

I like to use google scholar for literature searches:
http://scholar.google.com/scholar?hl=en&q=straight+skeleton+sweep+line&btnG=Search&as_sdt=400000000000&as_ylo=&as_vis=0

The first two hits appear spot on to me after skimming them:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.5505&rep=rep1&type=ps

http://www.springerlink.com/index/796W76637460T384.pdf

Look at the references of these papers and papers citing them (using features of google scholar or equivalent literature search engines) to find similar papers.  Often it is a paper that is written later that contributes very little itself that will explain things clearest or help you understand something that was confusing in the original publication of an algorithm.  Early papers tend to focus on proofs while later papers focus on implementation details and practical considerations.

Regards,
Luke