0xDE
21 April 2014 @ 11:33 am
I just added a new article to Wikipedia on indifference graphs (also known as unit interval graphs or proper interval graphs): the graphs formed from sets of points on the real line by connecting every two points whose distance is less than one.



There are many papers on algorithms for going from the graph to a geometric representation in linear time. The following method for the reverse problem, going from the set of points (or equivalently unit intervals) to its graph must be known, possibly in the context of its generalization to higher dimensional unit disk graphs, but I don't know a good reference for it.

Read more...Collapse )

Update, April 22: It appears that the correct reference for this is Bentley, Jon L.; Stanat, Donald F.; Williams, E. Hollins, Jr.
The complexity of finding fixed-radius near neighbors. Information Processing Lett. 6 (1977), no. 6, 209–212.
 
 
0xDE
19 April 2014 @ 02:07 pm
As I promised earlier, here is the video for my talk on "structures in solution spaces" at the Conference on Meaningfulness and Learning Spaces last February.



It was a wide-ranging talk, about learning spaces, distributive lattices and Birkhoff's representation theorem for them, rectangular cartograms, antimatroids, the 1/3-2/3 conjecture for partial orders and antimatroids, partial cubes, and flip distance in binary trees and point sets. It was also about an hour long, so don't watch unless you have the time. For those with shorter attention spans, I've also put up a pdf file of my talk slides.

The rest of the talks from the conference are also online. For those who like me are interested in discrete mathematics and discrete algorithms, Fred Roberts' talk on when the output of an algorithm is meaningful and Jean-Paul Doignon's talk on polyhedral combinatorics might be particularly interesting.
 
 
0xDE
13 April 2014 @ 11:50 pm
Every year about this time, my campus holds a spring celebration, with all the student organizations setting up pavilions in the park to sell food and advertise for new members, with the creative anachronists bashing each other with padded swords, and with a car show. Why a car show? I don't know, but I always enjoy seeing the variety of shapes and colors compared to today's mostly-the-same boxes. My favorite this year was a 1950 Chevy Fleetline, found rusting in a swamp in Tenessee; after a lot of work restoring it, its owner decided to cover it in clear-coat, showing off the patina on its metal, rather than just painting it. And then drove it cross country, towing a trailer full of his stuff, to UCI where his girlfriend is a grad student.



The moustache is more visible in this one. And here are the rest of the photos.
 
 
0xDE
12 April 2014 @ 10:07 pm
When I last saw Tetsuo Asano, he was giving a research talk at WADS, and openly worrying that it might be his last one. We all thought it was because of mandatory retirement (still legal in Japan). But, it turns out, no. Instead, he's the new president of JAIST. Congratulations, Tetsuo!

I'll probably miss SoCG, in Kyoto this year, but for those who will be going, there will be an associated workshop in honor of Asano's 65th birthday.
 
 
0xDE
The power of two choices in load balancing is well known: If one throws n balls independently at a similar number of bins (as in hash chaining), some bin will typically have Θ(log n/log log n) balls in it, but if one draws two random bins for each ball, and places the ball greedily into the less-full of these two bins, the maximum load will be much smaller, Θ(log log n). And if one clairvoyantly chooses which of the two bins to place each ball into (or uses cuckoo hashing to move the balls around between their two bins as later balls come in) it is very likely that one can achieve only a constant load.

The log-log result is originally by Azar, Broder, Karlin, and Upfal, and is well explained in a survey by Mitzenmacher, Richa, and Sitaraman, "The power of two random choices: A survey of techniques and results", which includes three different proof methods. Here's a fourth, which is related to but I think different from witness trees.

Read more...Collapse )
 
 
0xDE
05 April 2014 @ 03:18 pm
I had been running Snow Leopard (OS X 10.6) on my Macs, because I wasn't convinced that later versions were much of an improvement in usability. But Apple has apparently stopped providing security updates for a version as old as mine, so this week I updated to Mavericks. So far I've encountered only minor glitches: the update lost a couple of configuration settings (the monitor arrangement for my two-screen desktop and the preferred browser on my laptop), I had to reinstall git and update python, and some very old PowerPC software that I had forgotten I even had either stopped working or became more obviously flagged as non-working.

In honor of the successful upgrade, and Apple's new naming theme, here's some big-wave action at a closer beach (about five miles as the crow flies from my house).

Tags:
 
 
0xDE
This one isn't my problem – it came from MathOverflow – but it's frustrating me that I haven't been able to solve it, so I hope by reposting it here I can get some more attention to it and maybe even a solution.

The question is: let Fk be the family of graphs having no minor in the form of a cycle with doubled edges, of length k. Do the graphs in this family have a polynomial number of cycles (with the exponent of the polynomial depending on k, ideally linear in k)?

Read more...Collapse )

ETA 2014-04-10: Solved, negatively, by a planar bipartite permutation graph.
 
 
0xDE
28 March 2014 @ 11:07 pm
I'm back now, but this beach house in Barbados was my home for the last week, as I attended the 29th Bellairs Winter Workshop on Computational Geometry (my first time there).



Read more...Collapse )
 
 
0xDE
19 March 2014 @ 10:10 pm

The cages are a class of graphs that I think deserve to be more widely known, because they have a lot of interesting properties that make them useful as counterexamples in graph algorithms and graph theory. They're hard to construct and we don't have a lot of explicit descriptions of them, but that's not so important when you're using one as a counterexample.

Read more...Collapse )
 
 
0xDE
08 March 2014 @ 07:46 pm

Today I've been playing with the induced subgraphs of the Clebsch graph. Several other interesting and well-known graphs can be obtained from it by deleting a small number of vertices and forming the induced subgraph of the remaining vertices.

Read more...Collapse )
 
 
0xDE
01 March 2014 @ 05:51 pm
Many of the talks at the Conference on Meaningfulness and Learning Spaces that I recently attended concerned (surprise!) meaningfulness. The basic idea is to provide a crude filter for bad science and bad statistics by determining whether applying a formula to data could possibly make any sense. For instance, in many computer science conference program committees, we score papers on a scale from -3 to +3 (say) and then rank the papers by averaging the scores of different reviewers (possibly weighted to counter reviewer bias). Is this aggregation operation a meaningful thing to perform on this kind of data? Is it meaningful to say "it's twice as hot today as it was yesterday"? When we use an algorithm to solve a problem, how can we tell whether the result is meaningful?

Read more...Collapse )
Tags:
 
 
0xDE
28 February 2014 @ 01:11 pm
This week I've been attending the Conference on Meaningfulness and Learning Spaces at UC Irvine, in honor of the 80th birthday of my co-author Jean-Claude Falmagne. I believe videos of the talks will eventually be online and I'll put up a link to mine when that happens.

Jean-Claude himself gave a talk, in which the following cute geometric fact came up as an example: If f(x, y) is the function that computes the length of the hypotenuse of a right triangle with side lengths x and y, then f obeys the associative law. It's not difficult to see this from the algebraic form of the function, but Jean-Claude instead presented a geometric demonstration of this fact, based on the properties of an orthoscheme, a tetrahedron with four right triangles as its sides.

Read more...Collapse )
 
 
 
0xDE
23 February 2014 @ 07:25 pm

One of Oded Schramm's less-well-known but better-named results is his "monster packing theorem", a far-reaching generalization of the famous circle packing theorem of Koebe, Andreev, and Thurston.

Read more...Collapse )
 
 
0xDE
17 February 2014 @ 07:24 pm
While in Tucson, I took a tour of the University of Arizona's Steward Observatory Mirror Laboratory, where they built the mirrors for the big astronomical observatories such as the Giant Magellan Telescope. Two GMT mirrors were in progress and one had been shipped, but the one they were grinding when I visited was for a different instrument, the Large Synoptic Survey Telescope.



Its bizarre shape, with two paraboloids meeting in a central ridge, comes from the fact that it's really two mirrors in one: an annular 8.4m primary surrounding a 5.0m tertiary. The hexagons visible in the glass are a honeycomb pattern of molded holes on its back side, used to keep the mirror lightweight while maintaining rigidity. The honeycomb seems to be aligned with the edge of the mirror all around its circumference, with breaks in the pattern in the interior; it looks like maybe they're using some sort of centroidal Voronoi tessellation?

(A few more photos)
 
 
0xDE
16 February 2014 @ 06:37 pm
Here's a belated valentine-themed cappucino from Caffe Luce in Tucson, where I spent the last week visiting Stephen Kobourov, Alon Efrat, and their students and postdocs. (Also recommended: El Charro for dinner and Prep & Pastry for breakfast. Try the poutine!)

 
 
0xDE
07 February 2014 @ 10:31 pm
Yesterday I went to LACMA, mostly to see the James Turrell exhibit there. If I had been allowed, I would have taken many photos, but probably very few of them would have come out well, because Turrell's work is about light as a physical presence and about the human perception of color, and I don't think either of those things translates very well from camera to screen to eye.

As a case in point, one of his pieces was a large room, shaped roughly like a flattened cylinder, with a square portal entrance at one end (up a flight of steps from its anteroom). From below, waiting our turn to go in, the room seemed to be drenched in saturated color, changing from blue to pink to red, so thick that you expected the people inside to swim in it like honey rather than just walking in air and light. But from the inside, the room seemed mostly white or a bit off-white, with the end opposite the portal open to what seemed a bluish formless and infinite void. The values of light and dark within the room and the space beyond the room changed, but not so much its colors, except that if you paid attention the skin tones of the other participants were a bit off and one young woman's pale pink hoodie glowed with an unearthly radioactive fluorescence. How do you capture that experience in pixels?

I did take some shots of other exhibits, though. The one below is from Agnès Varda in Californialand, a show in which French New Wave filmmaker Agnès Varda built a shack from reels of one of her less successful films, Lions Love.



The rest of the photos include more of Varda's piece, and a couple of pieces from another exhibit in the same part of the museum on art inspired by the coming soccer World Cup.
 
 
0xDE
21 January 2014 @ 06:07 pm

A comparison sorting algorithm is called adaptive if its performance can be better than the worst-case O(n log n) time for comparison sorting algorithms, on subsets of inputs that are somehow close to being already sorted. Two examples of this are a Cartesian tree based sorting algorithm described by Levcopoulos and Petersson in WADS 1989, and splaysort, a splay tree based sorting algorithm described by Moffat, Eddy, and Petersson in Software: Practice and Experience 1996. How do these two algorithms compare with each other?

Read more...Collapse )
 
 
0xDE
19 January 2014 @ 02:34 pm
Miscellaneous links, not big enough for their own postings:

OMG is in the OED. But lest you think this is a triumph of netspeak over proper English, the earliest citation for it is dated 1917.

John McPhee on finding structure in the subjects he writes about. Probably helpful for all kinds of technical writing, not just the more popular nonfiction McPhee is known for.

Harry Lewis on the conflicts of interest inherent in the collaborations between academic institutions and repressive anti-free-speech regimes such as the ones in the Middle East, Singapore, or Kansas.

A requiem for the American dream, by Hunter on the Daily Kos.

Complementing my recent posts on SODA 2014, here are some reactions by others: Abstract talk. Notes by Mahnush Movahedi. And Cora on the message we're sending by having an all-male keynote slate.
 
 
0xDE
I guess it's been long enough since the Wave collapse, the Reader closure, and the Google news archive elimination, so it's time once again for Google to pick something else that is useful but only to an insufficiently massive subset of its users, and kill it. The latest dead Google baby is Google Notifier, which I've been using to get desktop notifications of new incoming emails. Google's suggested replacement is to enable desktop notifications directly in gmail, but that only works when I have a browser window or tab open to gmail, and I don't like cluttering up my browser with windows or tabs that I'm not actually using.

Oh well, the likely result is only that I'll be slow answering emails, something that is often true anyway. At least they haven't tried to break Google scholar yet.
Tags: