Linkage

Polyhedra with all but one dihedral specified (\(\mathbb{M}\)). Answering Robin Houston on MathOverflow, Dmitrii Korshunov proves that this information restricts the remaining dihedral to a finite set. Because there are infinitely many angles that can be realized as the only nonright angle of a polyhedron, this implies that these realizations may require arbitrarily many edges.

Gödel’s Lost Letter on the work of U. Washington PhD student Sally Dong and her coauthors applying modern convex optimization methods to construct circle packings (\(\mathbb{M}\)). It was known from older work of Mohar that the primaldual circle packing representation of any 3connected planar graph can be computed numerically in polynomial time (up to the desired precision of the solution) by an iterative method involving the vector of radii of the circles, but Mohar is kind of vague about the polynomial. The new method is limited to the special case of maximal planar graphs, but based on that it can compute (primal only) representations of any planar graph. It takes time within logarithmic factors of \(n\log(R/\varepsilon)\), where \(n\) is the number of circles, \(R\) is the radius ratio of the circles, and \(\varepsilon\) parameterizes the numerical accuracy of the solution. Here \(R\) can be exponential in \(n\), so this should really be thought of as quadratic time.

Slides from my talk at OSME (\(\mathbb{M}\)), surveying computational hardness results for origami folding and providing new \(\mathsf{PSPACE}\)hardness results for moving from one flatfolding to another.

The journal version of my paper “Noncrossing Hamiltonian paths and cycles in outputpolynomial time” (\(\mathbb{M}\)) from SoCG 2023 is now available openaccess from Algorithmica. This quick journal publications was made possible through two programs: Algorithmica’s, to fasttrack submissions from major algorithms conferences (while still providing the full refereeing process one would expect and hope for), and my university’s, to pay the openaccess fees for Springer journals. (I have a grant but it does not have funding allocated for this purpose.) I prefer diamond openaccess or (as in the case of LIPIcs) atcost rather than forprofit open access, and I’m aware that I’m privileged to be at an institution that can pay these fees, but as long as I am I think I should take advantage of it to make my work widely available at no cost to readers. As for the fast track: It was my first experience with that process, but it did not feel different than typical conference special issues, and I was happy with the thorough reviewing I received. I think encouraging more theoreticians to produce archival journal versions of their papers rather than leaving only more preliminary conference versions available can only be a good thing.

If you have any goo.gl links on your web content, now would be a good time to expand them before they stop working next year (\(\mathbb{M}\), via). I checked my blog and found only one, from a 2014 comment pointing to a site that went defunct in late 2016 and for which that page appears not to have been archived, so that may just be dead unless Pat Morin has saved it somewhere else. But at least the expanded url is more informative than the unexpanded one. Let that be a lesson not to use url shorteners. They don’t save you any characters on Mastodon (all urls count the same), they hide information from readers, and they’re more fragile. Among the url expanders I tried in tracing this one, I found wheregoes.com to be the most useful, because it showed all the intermediate expansions, not just the final one to the “we’re gone!” tiddlyspace page.

The Japan Institute of Heterocyclic Chemistry contracted with digital preservation site CLOCKSS to rehost its journal Heterocycles in the event of the institute’s site going offline for six months or more, and then sued when CLOCKSS did exactly what they were contracted to do (\(\mathbb{M}\), via).

Has nobody in origami engineering noticed that what they call the Kresling fold is an \(n\)gonal version of what others call the Schönhardt polyhedron (\(\mathbb{M}\))? Twist the two ends of an \(n\)gonal prism (keeping them parallel) and connect the twisted ends by a ring of triangles with alternating convex and concave dihedrals. For \(n=3\) this is a Schönhardt polyhedron. In general the result (as a thin shell with flexible creases) will have two stable configurations separated by an energy barrier but with certain spin angles it is instead monostable and shaky. Many videos are online; here’s one by Hiromi Yasuda showing both bistable and shakymonostable versions for \(n=6\).
The two stable states can differ significantly in distance between cylinder ends, creating a mechanism that can flatten or extend, changing volume as it does. This leads to many engineering applications, often stacking modules endtoend. Pressure changes or magnets can push the mechanism to jump to its other state. Mirrored pairs of modules can keep the ends untwisted; stacked variants can have more than two stable forms or control the order of collapse and extension. Biruta Kresling wrote about this form in the 2nd OSME, “Folded and unfolded nature”, 1994, and in other papers from the late 1980s or early 1990s , but bistability of the Schönhardt polyhedron is in Branko Grünbaum’s “Lectures on Lost Mathematics”, 1975, and the shaky form is from Schönhardt and Karlis Johansons in the 1920s. Unfortunately my searches failed to find any source connecting the names Kresling and Schönhardt. I’d like to add this connection to Wikipedia, but for that I need published sources.

On the constructivity of spacefilling curves (\(\mathbb{M}\)). Linked five months after it was posted due to a Mastodon glitch that temporarily showed a bunch of old posts, leading me to see it again.

A month or two ago I replaced my espresso grinder, an old Rancilio Rocky, by a Niche Zero, expecting only somewhat improved ease of use (\(\mathbb{M}\)). I did get that, but beyond that, I found that its ability to make finegrained adjustments in grind settings has led me to time my shots more consistently (in order to make those adjustments) and to produce consistently better shots. And its bigger range of grind settings and ease of tuning them to different batches of coffee beans has led me to greater experimentation in the beans that I use, rather than (as previously) settling on a single brand that I could rely on to work with my equipment. So let it be noted that sometimes seemingly small quantitative improvements in ease of use can lead to bigger and more qualitative improvements in other factors. Also, I’m currently loving the Axil Seasonal Espresso I brought back from Melbourne and a little sad that I chose to bring back only 1/2 kg instead of a whole kg. And did you know that the famous quote about mathematicians and coffee is by Rényi, not Erdős and not Halmos?

In case anyone else reading this happens to be acting as an endorser for an ACM distinguished member nomination (\(\mathbb{M}\), due August 1): be very careful with all the checkboxes on the web endorsement form before you click the submit button. Whoever designed the form has set a trap for you: along with what you think are the important parts of the form (your identity and the text of your endorsement), there are lots of little seeminglyunimportant checkboxes. But if you set any of them incorrectly, it will invalidate your endorsement. And then it will let you submit an invalid endorsement, and once you do that you will be unable to go back and change the checkboxes to make it valid. If you try, it will tell you that you already submitted the endorsement and cannot do it again. I did this and I’ve been told that at least one more endorser for the same nomination also did this, which makes me suspect I am far from alone in getting trapped this way. After trying multiple email addresses at ACM and pulling the “I’m an ACM Fellow” card I found a helpful staffer to get my endorsement fixed but that took more time and effort than filling in the form.
So, endorsers: be careful. And web designers, especially for leading computer science organizations for whom bad web design should be embarrassing: do not allow irrevocable submissions of superficially ok but actually invalid data. If you really want people to be able to record their nonendorsement, that should be an entirely separate process.

Some street art from Hawthorn (a suburb of Melbourne) from my recent trip to OSME (\(\mathbb{M}\)).

Spoiler for Celtix #49 (\(\mathbb{M}\)): vg vf gur ybatnjnvgrq cresrpg fpber sbe znkPrygvk! (rot13)

Gyroid 7direction pencil holder, Dan Piker.

The huckleberry structure, a buckled hexagonal paper cylinder with curved folds. I’m just waiting for the usual crew of Tachi, Mundilova, et al. to analyze it and prove that it exists mathematically as a developable surface.

When I make illustrations for my papers, I generally need them in pdf format (\(\mathbb{M}\)). But my preferred workflow is to save in svg format, compact the file down with svgo, and then convert them to pdf with an ancient cairobased script, svg2pdf (the one you get from
brew install svg2pdf
). This way I get tiny files as a result and they don’t bloat the size of my compiled .tex. And the svg files are useful for other purposes: web pages and Wikipedia articles. But this conversion script (or maybe the version of cairo it depends on) has some pretty severe limitations. For one, it doesn’t handle text well at all. For another, I recently learned that it doesn’t work when your svg file has a group (g tag) marked with an opacity. If it encounters that, it silently stops converting things and presents you with part of your graphics as output. When that happens, and I can’t find a way to fix the svg, I have to resort to saving as pdf from Adobe Illustrator and living with the resulting file bloat.Maybe there is a more robust svgtopdf convertor I should be using instead? Searching around, I realize I wrote about very similar issues in 2017 but maybe the ensuing years have led to better software?

Bézier curve arc length parametrizations (\(\mathbb{M}\)) and the impossibility of representing them with a closedform formula.