December 17, 2014

8:17 AM | Linked polytopes and toric grid tessellations
In my recent posting on four-dimensional polytopes containing linked or knotted cycles of edges, I showed pictures of linked cycles in three examples, the (3,3)-duopyramid, hypercube, and (in the comments) truncated 5-cell. All three of these have some much more special properties: the two linked cycles are induced cycles (there are no edges between two non-consecutive vertices in the same cycle), they include all the vertices in the graph, and their intersection with any two- or […]
4:46 AM | Survey on k-best enumeration algorithms
When I was asked earlier this year to write a short survey on k-best enumeration algorithms for the Springer Encyclopedia of Algorithms, I wrote a first draft before checking the formatting requirements. It ended up being approximately five pages of text and seven more pages of references, and I knew I would have to cut some of that. But then I did check the format, and saw that it needed to be much shorter, approximately two pages of text and a dozen references. I don't regret doing it this […]

December 16, 2014

6:25 AM | Linkage for mid-December
The number theory behind why you can't have both perfect fifths and perfect octaves on a piano keyboard (with bonus lattice quotient music theory link; G+)Sad news of Rudolf Halin's death (G+)Frankenstein vs The Glider Gun video (G+)Günter Ziegler on Dürer's solid (WP; MF; G+)Nature will make its articles back to 1869 free to share online, for certain values of "free" that you might or might not agree with (G+)Albert Carpenter's polyhedron models (G+)The only complete proof from […]

December 13, 2014

11:53 PM | Links and knots in the graphs of four-dimensional polytopes
The surface of a three-dimensional polyhedron is a two-dimensional space that's topologically equivalent to the sphere. By the Jordan curve theorem, every cycle of edges and vertices in this space cuts the surface into two topological disks. But the surface of a four-dimensional polytope is a three-dimensional space that's topologically equivalent to the hypersphere, or to three-dimensional Euclidean space completed by adding one point at infinity. So, just as in conventional Euclidean space, […]

December 05, 2014

7:27 AM | A strike against ERGMs
The exponential random graph model is a system for describing probability distributions on graphs, used to model social networks. One fixes a set of vertices, and determines a collection of "features" among the edges of this fixed set (such as whether or not a particular edge or combination of a small number of edges), each with an associated real-valued weights. Then to determine the probability of seeing a particular graph, one simply looks at which features it has; the probability is exp(sum […]

December 01, 2014

2:20 AM | Linkage for the end of November
Gamergate's attackers move on from (female) indie game developers to (female) game researchers (G+)Scammy publisher uses your name as the author of fake papers (G+)Escher-like impossible figures by Regalo Bizzi based on a triangular grid (G+)James Turrell installation in Las Vegas (G+)Waiting for Godot: The Game (by Zoe Quinn; G+)Fedorov's Five Parallelohedra, a complete classification of the shapes that can tile space by translation (G+)On the high variance in journalistic standards for […]

November 27, 2014

7:25 AM | Trees that represent bandwidth
In my algorithms class today, I covered minimum spanning trees, one property of which is that they (or rather maximum spanning trees) can be used to find the bottleneck in communications bandwidth between any two vertices in a network. Suppose the network edges are labeled by bandwidth, and we compute the maximum spanning tree using these labels. Then between any two vertices the path in this tree has the maximum bandwidth possible, among all paths in the network that connect the same two […]

November 25, 2014

8:12 AM | LIPIcs formatting tricks
If, like me, you're working on a SoCG submission, and this is the first time you've tried using the LIPIcs format that SoCG is now using, you may run into some minor formatting issues (no worse than the issues with the LNCS or ACM formats, but new and different). Here are the ones I've encountered, with workarounds where I have them:The LIPIcs format automatically includes several standard LaTeX packages including babel, amsmath, amsthm, amssymb, and hyperref. So there's no point in including […]
6:00 AM | Thin folding
I have another new preprint on arXiv this evening: Folding a Paper Strip to Minimize Thickness, arXiv:1411.6371, with six other authors (Demaine, Hesterberg, Ito, Lubiw, Uehara, and Uno); it's been accepted at WALCOM.The basic goal of this is to try to understand how to measure the thickness of a piece of paper that has been folded into a shape that lies flat in the plane. For instance, in designing origami pieces, it's undesirable to have too much thickness, both because it wastes paper […]
9 Results