Generalized Straight Skeleton

Question

The straight skeleton of a polygon can be computed by having the edges of the polygon move inwards at a uniform constant speed.

Is it useful to generalize this computation process by varying the speeds at which the edges move inward? That is, every edge will move at some nonzero speed of its own, which could even be negative. Has the "generalized straight skeleton" generated from this algorithm been studied before?

Answer 1

It seems that these are called weighted straight skeletons. I'm not sure where they were introduced; it might be this article, "Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions". Here's a blog with pretty pictures: http://twak.blogspot.com/2011/01/degeneracy-in-weighted-straight.html

Answer 2

History.

To the best of my knowledge weighted straight skeletons were first investigated in an article by David Eppstein and Jeff Erickson, Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions in Discrete Comput. Geom., 22(4):569–592, 1999. (There was a conference version at SCG'98, too.)

There is a paper by Biedl et al., Weighted Straight Skeletons In the Plane, Comp. Geom. Theory & Appl. pp. 120--133, vol. 48(2), 2015, which investigates properties of weighted straight skeletons and illustrates some pitfalls in the straight-forward definition. The final step to give a complete definition was done in Biedl et al., Planar Matchings for Weighted Straight Skeletons, Int. J. of Comp. Geom. & Appl. pp. 221--229, vol. 26(3 & 4), 2016.

Main difficulties.

In my opinion there are two main difficulties when generalizing to weighted straight skeletons:

1. Positively weighted straight skeletons share many properties with unweighted straight skeletons, while most properties do not carry over to the negative case. Table 1 in Weighted Straight Skeletons In the Plane gives an overview.

   For example, consider the following figure:

   

   It shows a polygon and its straight skeleton with negative weights. (Actually, the roof model is shown; if you project the blue lines onto the xy-plane you get the skeleton.) The polygon is simple (without holes) but the skeleton has cycles. If weights are positive then the straight skeleton of a simple polygon is a tree.

2. In the weighted case it is actually not obvious how the wavefront structure changes when so-called multi-events happen. In Planar Matchings for Weighted Straight Skeletons the problem is solved by a framework based on so-called planar matchings.

References.

An overview on the topic and related work (such as known algorithms) are given in the two papers by Biedl at al., in Palfrader's thesis and on this website: https://www.sthu.org/research/weighted-straightskeleton/

Palfrader's thesis, by the way, distinguishes between additively and multiplicatively weighted straight skeletons. Your question relates to multiplicatively weighted straight skeletons.

In Huber's thesis you can find more ways to generalize straight skeletons.