Thinking Outside the Plane: https://www.metafilter.com/183649/Thinking-Outside-the-Plane

Interesting roundup of 3d solutions to 2d problems, starting with Tarski's plank problem: Can you cover a diameter-\(n\) disk with fewer than \(n\) unit-width strips?

Sadly, they missed the 3d proof of Desargues' theorem: https://en.wikipedia.org/wiki/Desargues%27s_theorem#Three-dimensional_proof

There's also a 2d-3d connection with Miquel's six-circle theorem but I think it goes the other way: https://11011110.github.io/blog/2006/03/22/miquels-six-circles.html

New post: Don't walk, https://11011110.github.io/blog/2019/10/19/dont-walk.html

Probably of local interest only; a ranty photo-essay about how my campus has been making it more annoying to walk to work.

Quasiperiodic bobbin lace patterns: https://arxiv.org/abs/1910.07935, Veronika Irvine, Therese Biedl, and Craig S. Kaplan, via https://twitter.com/bit_player/status/1185356703065354240 — aperiodic tilings in fiber arts.

The attached image is a photo of lace (not an illustration), braided into an Ammann–Beenker tiling pattern.

New blog post: From one fold to another, https://11011110.github.io/blog/2019/10/16/from-one-fold.html

It describes my new preprint, "Face flips in origami tessellations" (with Akitaya, Dujmović, Hull, Jain, and Lubiw, https://arxiv.org/abs/1910.05667) on converting one mountain-valley assignment of a crease pattern into another by repeatedly flipping the folds surrounding a single face of the pattern.

Kotzig's theorem (https://en.wikipedia.org/wiki/Kotzig%27s_theorem): Every convex polyhedron has an edge whose endpoints have total degree at most 13. (New article on Wikipedia.)

You might think that (because average vertex degree in a convex polyhedron is < 6) there will always be an edge whose endpoints have total degree at most 11, but it's not true. As Anton Kotzig proved in 1955, the answer is 13. A worst-case example is the triakis icosahedron, whose minimum-degree edges connect vertices of degrees 3 and 10.

the American Mathematical Society just published a free ebook called Living Proof, a collection of mathematicians recounting their often turbulent paths to where they are now. i've read a few of the stories and i think this is an amazing read, not just for scholars of math, but for anyone who is doing something where they simply don't feel "smart enough" to succeed. success is often made up of struggle and failure; this can be difficult to remember in our current times.

New blog post: Hardness of planar Hamiltonian decomposition and linear arboricity, https://11011110.github.io/blog/2019/10/12/hardness-planar-hamiltonian.html

An NP-completeness proof that turned out to be too easy to write up as a paper, even though it solves a 2012 conjecture.

Huh, I'm so used for mailing list emails to use tracking links, that it's so refreshing that the #EFF's emails use plain URLs.

Anyway, point being, this is an EFF article about how the US is trying to pass legislation to shift responsibility away from people when their software discriminates against them. @bgcarlisle , I believe this is your métier.

https://www.eff.org/deeplinks/2019/10/tell-hud-algorithms-are-no-excuse-discrimination

New math post on my blog: Incenters of chocolate-iced cakes https://blog.plover.com/math/cake.html

Two speakers censored at AISA, an Australian information security conference: https://www.schneier.com/blog/archives/2019/10/speakers_censor.html

One of them is Australian, the other not. They were both scheduled to talk long before and cancelled after a last minute demand from the Australian Cyber Security Centre.

As Bruce Schneier writes, this kind of action merely calls attention to their work and makes the Australian government look stupid and repressive while doing nothing to actually increase security.

Drawing clustered graphs of bounded width: https://11011110.github.io/blog/2019/10/07/drawing-clustered-graphs.html

New blog post about my new preprint with Da Lozza, Goodrich, and Gupta on clustered planarity, https://arxiv.org/abs/1910.02057. It won best paper at IPEC last month, but just in time: while it was in submission Fulek and Tóth put out their own preprint giving a polynomial time algorithm for clustered planarity without any dependence on width or other parameters.

My new dining room ceiling lamp is a trefoil knot! It's the "Vornado" LED lamp from WAC lighting (http://www.waclighting.com).

We chose it to replace a halogen lamp that shorted out, burned through its power cable, fell onto the table below it, and shattered hot glass all over the room, fortunately without causing a fire or seriously damaging the table and while the room was unoccupied.

Full photo set at https://www.ics.uci.edu/~eppstein/pix/trefoil/

Blind Folks and the Evolving Elephant: https://agtb.wordpress.com/2019/10/05/blind-folks-and-the-evolving-elephant-by-vijay-vazirani/

Guest post by my colleague Vijay Vazirani on the "Turing's Invisible Hand" blog, on the different perspectives brought by economics and computer science to problems of matching resource providers with resource consumers.

Revisiting Minesweeper: https://www.flyingcoloursmaths.co.uk/revisiting-minesweeper/

As Uncle Colin shows, calculating the probabilities of different scenarios for the boundary of the cleared region needs to consider as well the number of mines in non-boundary cells. Based on that, one can find the safest move, at least when there are few enough scenarios to list them all.

But it looks much harder to find the move most likely to lead to clearing the whole board, even for simple initial situations like the one he shows.

- Home page
- https://www.ics.uci.edu/~eppstein/

I'm a computer scientist at the University of California, Irvine, interested in algorithms, data structures, discrete geometry, and graph theory.

Joined Apr 2017