|
[Nov. 18th, 2014|08:59 am]
Jason
|
Discovered that the problem of
(a) given a floorplan, determine the 3d shape of the roof if the roof is to be made of flat pieces and have constant slope towards a wall everywhere
or similarly
(b) given a letter-shape, what is the natural way to make it look nicely engraved like so
is actually pretty subtle and interesting.
Here's a video:
People have made piles of papers on the computational geometry of "straight skeletons" and the related problem of "motorcycle graphs", which is basically the sober and unironic contemplation of the game Tron. It turns out both of these problems are P-complete but it has been too long since I took complexity theory to really have a feel for how powerful logspace reductions are, so I don't have a good sense of what that means. |
|
