How to turn complex polygon into simple polygon?

Fernando Cacciola (h) fernando_cacciola at
Tue Jun 10 17:42:47 PDT 2003


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
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list