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 )
 
 
0xDE
15 September 2014 @ 11:20 pm
 
 
0xDE
13 September 2014 @ 02:57 pm
Just some test shots with my new travel lens (Canon's 17-40/F4 L, replacing a mysteriously nonfunctional and optically not as good 17-85IS).

 
 
0xDE
09 September 2014 @ 10:15 pm
Did you ever wonder why different states of the US have the numbers of representatives in congress that they do? It's supposed to be proportional to population but that's not actually true: for instance the ratio of representatives to population is about 40% higher in Montana than California. What formula or algorithm do they use to pick the numbers?

Read more...Collapse )
Tags: ,
 
 
0xDE
05 September 2014 @ 11:47 pm
The Rado graph has interesting symmetry properties and plays an important role in the logic of graphs. But it's an infinite graph, so how can we say anything about the complexity of algorithms on it?

There are algorithmic problems that involve this graph and are independent of any representation of it, such as checking whether a first-order logic sentence is true of it (PSPACE-complete). But I'm interested here in problems involving the Rado graph where different ways of constructing and representing the graph lead to different algorithmic behavior. For instance: the Rado graph contains all finite graphs as induced subgraphs. How hard is it to find a given finite graph? Answer: it depends on how the Rado graph is represented.

Read more...Collapse )
 
 
0xDE
31 August 2014 @ 10:59 pm
More Google+ links from the last couple of weeks:
 
 
0xDE
28 August 2014 @ 10:46 pm
The last of my Graph Drawing preprints is also the first of the papers to see daylight from the workshop last spring in Barbados: "Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths" (arXiv:1408.6771, with Zachary Abel, Erik Demaine, Martin Demaine, Anna Lubiw, and Ryuhei Uehara).

Read more...Collapse )
 
 
0xDE
27 August 2014 @ 05:43 pm
If you're used to writing mathematics, but haven't paid much attention to model theory, you probably think a fully-quantified mathematical sentence is generally either true or false. Fermat's last theorem, for instance, can be written as the following sentence: For all positive integers a, b, c, and n, if n > 2, then an + bn ≠ cn. This sentence is fully quantified: the four variables a, b, c, and n are all covered by the quantifier "for all positive integers". It's one of the true ones, if difficult to prove.

But when we're working with the logic of graphs, a (fully-quantified) sentence is itself just another mathematical object, and its truth is relative: it might be true for some graphs and false for others. Read more...Collapse )
 
 
0xDE
26 August 2014 @ 10:35 pm
Another of my Graph Drawing papers is online today: "Planar Induced Subgraphs of Sparse Graphs", arXiv:1408.5939, with Cora Borradaile and her student Pingan Zhu. It's about finding large planar subgraphs in arbitrary graphs; in the version of the problem we study, we want the planar subgraph to be an induced subgraph, so the goal is to find as large a subset of vertices as possible with the property that all edges connecting them can be drawn planarly. Equivalently, we want to delete as few vertices as possible to make the remaining graph planar. It's NP-complete, of course, so our goal is to prove good bounds on how many vertices you need to delete rather than computing this number exactly.

Read more...Collapse )
 
 
0xDE
21 August 2014 @ 11:16 pm
The second of my papers for this year's Graph Drawing symposium is now online: "Balanced Circle Packings for Planar Graphs", arXiv:1408.4902, with Jawaherul Alam, Mike Goodrich, Stephen Kobourov, and Sergey Pupyrev. It's about finding circle packings (interior-disjoint circles whose tangencies form a given graph) where the radii are all within a polynomial factor of each other. Or equivalently, if one normalizes the packing to make the smallest circles have unit radius, then the area of the packing should be at most polynomial. We call packings with this property "balanced".

Read more...Collapse )
 
 
0xDE
18 August 2014 @ 05:22 pm
Yesterday, this year's Hugo Award winners were announced; this is an annual fan popularity contest for the best works in science fiction and fantasy (there is a different set of awards voted on by the writers themselves, the Nebulas). I have a few thoughts on the nominees (like, why wasn't Her among them?) but that's not what I'm writing about. Rather, what interests me in this year's contest is the issue of voting systems and their resistance to manipulation.

Some background: this year's award nomination and voting involved a group of fans from one of the subgenres of SF whose two main interests seem to be military jingoism and sexual and racial anti-inclusivity and who have apparently dubbed themselves the "sad puppies". These people pushed a slate of nominees onto the ballot, which then lost fairly decisively in the final voting. There was no unfair vote manipulation going on: everything was aboveboard and according to the rules. But it caused me to wonder: how large would a dedicated faction of the voters have to be to break into the winner's circle, against the will of the remaining voters?

Read more...Collapse )
Tags:
 
 
0xDE
15 August 2014 @ 10:00 pm
Some links I've posted over on Google+ over the last couple of weeks (and reposted here, among other reasons, because I don't trust G+ to give me a usable interface for finding all of my old posts there):
Tags:
 
 
0xDE
14 August 2014 @ 11:51 pm
My photos from the UBC Museum of Anthropology are online now. Here is a sampling of thumbnails:



The museum is mostly devoted to Pacific Northwest First Nations art, but as a living culture rather than as something that happened in the past, so it includes a mix of older cultural artifacts with more modern art. It also has a gallery of Pacific Rim cultures, and a couple of rotating exhibit spaces; for our visit, one of them was on "urban aboriginal youth" and the other was a show of Afro-Cuban art including two sculptures shown above. Definitely worth a visit if you're in the Vancouver area, despite the minor inconvenience of getting there from downtown (we took a city bus).
 
 
0xDE
10 August 2014 @ 09:13 pm
I just returned from a short vacation in Vancouver (unrelated to SIGGRAPH, also happening there now) and took a few snapshots, mostly of boats or totem poles. Another batch of photos from MOA, also with many totem poles, is still to come. But here's one that has neither:



Obviously, I don't understand the rules of photographic composition. By any rational standard, the tree should not be at the center. It's not the subject, it attracts too much attention to itself there, and centering typically makes the image very static. But when I cropped the shot (mostly to put it into this panoramic aspect ratio) the tree insisted that that's where it had to be. I don't understand why. Also, the small bush on the right, that seems like a distraction, is necessary. I had another version of this image from a slightly different perspective that eliminated the bush, and it didn't work as well. Again, I can't explain why.

Some other Vancouver stuff I enjoyed but didn't photograph: visiting artists' studios, sampling artisinal sake, and learning about summer tree-planting jobs from another sake taster, on Granville Island (do it on a weekday); Shakespeare in the park (The Tempest, but they're also showing Midsummer Night's Dream if you haven't already seen that one more times than you can count); sushi at Miku (across the street from my hotel) and bubble tea next door (we have plenty of that at home but this one had even more variety); Douglas Coupland's big art show at the Vancouver Art Gallery (apparently he's not just a famous author); and waffles and berries for breakfast (there are several cafes that specialize in this — the one we chose was on Pender between Nicola and Broughton).