When this happens, we can use it to construct a nice two-dimensional grid representation of the polytope.

**( Read more...Collapse )**

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 )**

When this happens, we can use it to construct a nice two-dimensional grid representation of the polytope.

Leave a comment

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.

15 December 2014 @ 10:25 pm

- 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 Fermat and the gaps in arithmetic progressions of squares (G+)
- Mark-Jason Dominus on how and why he negotiated with his book publishers to be able to keep a free online copy of his Perl book (G+)
- Video on drawing mushrooms with sound waves (G+)
- Senate staffer tries to scrub "torture" reference from Wikipedia's CIA torture article (G+)
- Numberphile video on origami angle trisection (G+)
- Video on the world's roundest object and why it was made (G+)
- How much text re-use is too much? A statistical study of plagiarism on arXiv (via; G+)

13 December 2014 @ 03:53 pm

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.

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 )**

30 November 2014 @ 06:20 pm

- 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 plagiarism (G+)
- How many median graphs are there? (G+)
- SODA/ALENEX/ANALCO 2015 preregistration closes Monday, Dec. 1 (G+)

(G+)- Hexagonal diamond, a crystalline carbon structure even harder than true diamond (G+)
- The Laves graph, an infinite symmetric 3-regular graph that forms yet another possible carbon crystal (G+)

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 )**

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 )**

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)

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.

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.

15 November 2014 @ 10:03 pm

- An experiment in allowing journal reviewers to reveal their names (the G+ post has several additional links on academics including some well known graph theorists taking money to deliberately distort university rankings)
- Pumpkin geometry: stereographic projection of shadows from carved balls (G+; no actual pumpkins involved)
- Clint Fulkerson: an abstract artist whose work feels somehow both geometric and organic (G+)
- Paper popups by Peter Dahmen (G+)
- Crochet Platonic polyhedra by June Gilbank (G+)
- Advice for combining autoref with shared counters for theorems and lemmas (and in the G+ post, a plea for something similar that will work with the LIPIcs LaTeX format)
- A topological trick with duvet covers (G+)
- Harborth's conjecture on graph drawing with integer edge lengths (G+)
- A cryptic crossword by Thore Husfeldt featuring parameterized complexity and my name (G+)
- Giving scientific advice that turns out to be incorrect is not a crime (G+)
- Chvátal-Sankoff constants (the expected length of a random longest common subsequence; G+)
- Automatic Voynich (G+)
- Magic squares on stamps (G+)
- Polyhedra in which all faces are holy, and an update on big Life spaceships (G+)
- Photos of mechanical calculators (via Wired and BB; G+)

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 )**

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?

01 November 2014 @ 10:47 am

- Kinetic origami sculpture by Jo Nakashima (G+)
- How pineapples help finding Steiner trees (G+)
- ICALP 2015 conference web site and call for papers (deadline Feb.17; G+)
- Mass resignation from an open access journal (G+)
- A hardness result for organizing your Google Scholar profile (G+)
- Wikipedia, a Professor's Best Friend, and a tangential note about binary logarithms (G+)
- When women stopped coding, an analysis of why and how long we've been seeing a decline in the number of women in computer science (G+)
- Fake classes for athletes at UNC, or why I'm happy UCI doesn't have a football team (G+)
- WADS 2015 conference web site and call for papers (deadline Feb.20; G+)
- City maps colored by grid orientation (MF; G+)
- Scientist sues open-peer-review site commenters (G+)
- Wikipedia emerges as trusted internet source for ebola information (G+)
- Was the Knuth-Plass line breaking output ever subjected to a blind experiment? (G+)
- At the far ends of a new universal law, a popular-press article about the Tracy–Widom distribution (G+)
- Brands of nonsense, on university's attempts to apply corporate branding dogma to themselves (G+)

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 )**

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?

15 October 2014 @ 01:30 pm

- Why academic writing stinks or, keep it simple (G+)
- Sad news of the death of Ferran Hurtado (G+)
- A visual compendium of glowing creatures, scientific illustration by Eleanor Lutz (G+)
- Women in computer science get tenure at significantly lower rates than men even after normalizing for research productivity (G+)
- Tietze's graph, Wikipedia article expanded with a new illustration of why it has the name it has: it was an earlier counterexample in the theory of coloring graphs on non-orientable surfaces (G+)
- Abdel Kader Haidara awarded Germany's 2014 Africa Prize for rescuing Timbuktu manuscripts (G+)
- Adobe Digital Editions 4 spying on users by sending a listing of the contents of your entire digital library in cleartext (G+)
- NASA Invents a Folding Solar Panel Inspired by Origami (G+)
- Optimal randomized comparison sorting: a question on the CSTheory exchange observing that randomization can break the decision tree lower bound and asking what's known about upper bounds (G+)
- More on the strange scale-free Babylonian concept of number, in which 1 and 60 were apparently indistinguishable (G+)
- Robert le Ricolais’s Tensegrity Models, architectural models that could as well be abstract art (G+)
- European Science Foundation demands retraction of criticism in Nature, threatens legal action (G+)
- SoCG 2015 conference web site and call for papers (G+)

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 s^{e} 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 )**

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 s

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.)

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 )**

30 September 2014 @ 08:09 pm

- Algomation animated algorithms (G+)
- Rush hour video, or, what our robot-driven future will be like (G+)
- The Washington Post rants about those evil student pirates, but neglects to mention the free alternatives (G+)
- A song video about knots, from the low-dimensional topology blog (G+)
- Fun hex grid facts, via MF (G+)
- SODA 2015 accepted papers (G+)
- KaTeX, a lobotomized but fast web math renderer (G+)
- Against laptops in lectures, via MF (G+)
- David Wade’s ‘Fantastic Geometry’ – The Works of Wenzel Jamnitzer & Lorenz Stoer on Dataisnature (G+)
- Something about how some data structures I helped develop could improve bitcoin mining (G+)
- 63 and –7/4 are special, numberphile video about prime factors of recurrence sequences (G+)
- Critique of Hirsch’s Citation Index, article in the
*Notices*about how the h-index doesn't provide much more information than the total citation count (G+)

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:

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

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 )**

20 September 2014 @ 08:05 pm