How to turn complex polygon into simple polygon?

[Fernando Cacciola (h)]

Greetings,

The Eppstein's and Erickson's paper "Raising Roofs, Crashing Cycles and
Playing Pool" present an algorithm for the construction of the straight
skeleton of arbitrary planar figures.
The paper identifies a special degenerate case were two or more split events
reach the same point simultaneously (and nothing else), defining a special
kind of event called a "vertex event".

For robustness reasons, I'm trying to figure out a definition of vertex
event which does not involve distance computations between computed points
(i.e: does not check for equality of slit points).

AFAICT, a split event ocurrs when two consecutive edges moving along a
reflex bisector simultaneously hit some oposite edge at a given offset
distance -or instant- 't'.
Thus, a reflex event is given by two consecutive edges EL,ER -called
defining edges- and some oposite edge EO.

My question is: is it true that a vertex event ocurrs ONLY when the oposite
edge of a split event is either one of the defining edges of some other
split event which ocurrs at the same instant, and viceversa?

That is, is it a necessary condition that given split events ((Ei,Ej),En,t)
and ((Ek,El),Em,t),
for them to define a vertex event, 'En' is either 'Ek' or 'El', and 'Em' is
either 'Ei' or 'Ej'.

And is such a condition sufficient?


If such a condition is necessary and sufficient, that is, defines a vertex
event, I think it follows that there can be no more than two split events
collpased as a single vertex event. Or, to put it differently, there must be
an even number of simultaneous split events at the same point, each pair
defining a (topologically) distinct vertex event.
Is this correct?

Thank you.

Fernando Cacciola


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.