0xDE
17 December 2014 @ 12:17 am
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 three-dimensional face of the polytope forms a connected path.

When this happens, we can use it to construct a nice two-dimensional grid representation of the polytope. Read more...Collapse )
Tags:
 
 
0xDE
16 December 2014 @ 08:46 pm
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 way; I think having a longer version to cut down helped me to organize the results and figure out which parts were important. But then I thought: why not make the long(er) version available too? I added a few more references, so now it's about six pages of text and ten of references, still closer to an annotated bibliography than an in-depth survey. Here it is: arXiv:1412.5075.
 
 
 
0xDE

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, polygonal chains (such as the cycles of edges and vertices of the polytope) can be nontrivially knotted or linked. If so, this can also be seen in three-dimensions, as a knot or link in the Schlegel diagram of the polytope (a subdivision of a convex polyhedron into smaller convex polyhedra). Does this happen for actual 4-polytopes? Yes! Actually, it's pretty ubiquitous among them.

Read more...Collapse )
 
 
0xDE
04 December 2014 @ 11:27 pm
The exponential random graph model is a system for describing probability distributions on graphs, used to model social networks. Read more...Collapse )
 
 
0xDE
30 November 2014 @ 06:20 pm
 
 
0xDE
26 November 2014 @ 11:25 pm
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. Read more...Collapse )
 
 
0xDE
25 November 2014 @ 12:12 am
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:Read more...Collapse )
Tags:
 
 
0xDE
24 November 2014 @ 10:00 pm
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 causing your piece to be smaller than it needs to and because it may be an obstacle to forming features of your piece that are supposed to be thin.

The obvious thing to do is to just count the number of layers of paper that cover any point of the plane, but can be problematic. For instance, if you have two offset accordion folds (drawn sideways below)
/\/\/\/\/\
          \/\/\/\/\/
then it's not really accurate to say that the thickness is the same as if you just had one of the two sets of folds: one of the two folds is raised up by the thickness of the other one so the whole folded piece of paper is more like the sum of the thicknesses of its two halves.

In the preprint, we model the thickness by assuming that the flat parts of the paper are completely horizontal, at integer heights, that two overlapping parts of paper have to be at different heights, and that a fold can connect parts of paper that are at any two different heights. But then, it turns out that finding an assignment of heights to the parts of paper that minimizes the maximum height is hard, even for one-dimensional problems where we are given a crease pattern of mountain and valley folds as input, without being told exactly how to arrange those folds. The reason is that there can be ambiguities about how the folded shape can fit into pockets formed by other parts of the fold, and choosing the right pockets is difficult.
 
 
0xDE
15 November 2014 @ 10:03 pm
 
 
0xDE
09 November 2014 @ 01:12 am
Presumably many readers have seen and played the 2048 game, in which one slides tiles in different directions across a grid, causing certain pairs of tiles to combine with each other when their sum is correct (in this case, when the sum is a power of two):



Or if you get bored with it there are many other variations, some of which have different combining rules, for instance there's one where tiles only combine when their sum is a Fibonacci number. I have the impression this all started with another of these games, threes, which you would think allows tiles to combine when their sum is a power of three or twice a power of three (the ternary digits), but actually uses a different set, the numbers 1 or 2, and the numbers that are three times a power of two.

At some point I switched from 2048 to 987 (the Fibonacci one) and noticed that the games were lasting longer. Or alternatively, I could reach higher tile values in 987 more easily despite the fact that it takes twice as long (the 987 game gives you 1's for each new tile, instead of 2's and 4's for 2048). Why is that?

Read more...Collapse )
 
 
 
0xDE
26 October 2014 @ 04:21 pm
I've been playing with the Cayley graphs of the symmetric group again, after accidentally running across the Wikipedia article on the icositruncated dodecadodecahedron and thinking "oh yeah, that's the polyhedron that geometrically represents the Cayley graph generated by a transposition and a 4-cycle".



Only, it's not. That was a different star polyhedron. So is the icositruncated dodecadodecahedron also a permutohedron? And if so, what are the generators of the corresponding Cayley graph?

Read more...Collapse )
 
 
0xDE
15 October 2014 @ 01:30 pm
 
 
0xDE
14 October 2014 @ 04:17 pm
The idea of a 2-site Voronoi diagram was pioneered by Barequet, Dickerson, and Drysdale in a WADS 1999 paper later published in Discrete Applied Math. 2002. The basic idea is that you have a function d(p,q;x) that tells you the distance from an unordered pair of sites {p,q} to another point x in the plane; given a collection of sites, you want to divide the plane up into regions so that the region containing a point x tells you which pair of sites is closest to x (or in some cases farthest from x). Since their work there have been several followup papers including one in which I was involved.

If three sites are given, then these sites determine three pairs of sites, three regions in the Voronoi diagram, and (usually) one or more Voronoi vertices where all three sites meet. Often, these vertices define triangle centers: special points defined from the triangle of the three sites, such that applying a similarity transformation to the plane commutes with constructing the given point. Technically, to get a triangle center out of a 2-site Voronoi diagram, the distance function has to be invariant under congruences of the plane, and if a triangle pqx is scaled by a factor of s then the distance d(p,q;x) has to scale by a factor of se for some constant scaling exponent e (possibly zero). But this scaling requirement is true of many natural functions that you might want to use as distances.

By now, thousands of different triangle centers have been studied. Which of them can be generated from 2-site Voronoi diagrams in this way? Here are some examples. (The X(...) numbers are references to Clark Kimberling's Encyclopedia of Triangle Centers.)

Read more...Collapse )
Tags:
 
 
0xDE
08 October 2014 @ 05:57 pm
I've posted before about the Miura fold, a subdivision of a sheet of paper into paralellograms that gives a nice smooth motion from a compact folded state (in which the parallelograms are all folded on top of each other) to an unfolded state in which the paper is nearly flat. But this pattern can have defects that interfere with its folding pattern, in which small subunits of the pattern fold the wrong way: they still have the same creases but some of them are backwards. My latest arXiv preprint, "Minimum Forcing Sets for Miura Folding Patterns" (arXiv:1410.2231, with Ballinger, Damian, Flatland, Ginepro, and Hull, to appear at SODA) studies the number of creases that need to be forced to go the right way, in order to be sure of getting the correct Miura fold for the rest of the creases as well.

Read more...Collapse )
 
 
0xDE
30 September 2014 @ 08:09 pm
Tags:
 
 
0xDE
28 September 2014 @ 08:16 pm
I neglected to pack my camera and its new lens with me for the trip to GD (oops), and anyway most of the time the weather wasn't very conducive to photography. But I did take a couple of cellphone snapshots of graffiti/murals on the University of Würzburg campus. This one, if Google translate is to be believed, proclaims Würzburg as the city of young researchers; it's on the wall of the Mensa where we ate lunch every day.



And here's some advice to the students starting the new term, from just outside the conference hall:

 
 
0xDE
27 September 2014 @ 09:29 pm
I'm currently in the process of returning* from Würzburg, Germany, where I attended the 22nd International Symposium on Graph Drawing (GD 2014) and was one of the invited speakers at the associated EuroGIGA/CCC Ph.D. school on graph drawing.

Read more...Collapse )
 
 
0xDE
20 September 2014 @ 08:05 pm
Joe Malkevitch recently asked me: which polycubes have planar graphs?

Read more...Collapse )