0xDE
27 June 2014 @ 02:18 pm
Voting opened this week for members of the compgeom-announce mailing list, on whether the annual Symposium on Computational Geometry should leave ACM, as the Conference on Computational Complexity has recently done from IEEE.

There's a lot more opinion on both sides of the issue, and arguments both for staying with ACM and for leaving, in a series of postings at MakingSoCG. If you're a compgeom-announce member, please inform yourself and then make your own opinion known through the vote. Past votes on the same issue had unconvincing results due to low turnout; we don't want the same problem to happen again.
 
 
0xDE
26 June 2014 @ 10:02 pm
It must be graduation-and-moving-out time again. Seen this morning, in the parking lot of a UCI apartment complex for postdocs and visiting researchers:

 
 
0xDE
03 June 2014 @ 10:33 pm
While cleaning up some badly-sourced articles on Wikipedia, I ran across the one on reverse perspective, a strange drawing style in which nearby objects are shown as small and far-away objects are shown as big. Despite the strangeness, it's mathematically consistent: it's what you get when you put objects between the perspective point (your eye in conventional perspective) and the viewing plane (a window through which you're looking at the world). Here's a nice example:



Although it's been used a lot in art (sometimes deliberately, for effect, sometimes naively, and sometimes for reasons lost to history and hotly debated), I don't know of any attempts to use it for visualization. It has some effects that might be useful, notably the ability to see more sides of an object at once than is possible in a conventional view.
 
 
0xDE
25 May 2014 @ 11:59 am
PADS, my collection of Python algorithm implementations, has finally been updated to work under both Python 2 and Python 3. Most, but not all, of its modules have been tested under both version of Python.

Most of the code was already pretty close to working. The most frequent changes I needed to do: use next(iterator) instead of iterator.next(); avoid xrange, iteritems, and itervalues; use list(dict.items) for loops that change the dictionary; wrap arguments to print in parens.
Tags:
 
 
0xDE
It must be that time of year...Friday and today I took part in two more thesis defenses, for Brian Parrish and Paweł Pszona.

Brian is a mechanical engineering student, supervised by fellow Wikipedia editor Mike McCarthy. His thesis research was to develop a system that can automatically analyze the configuration space of an eight-bar linkage and determine whether it can smoothly move between a desired set of poses. Somehow I got involved because setting up a system of equations describing the motion of these linkages involves some interesting graph algorithm problems. He's been working at Northrop Grumman, who supported him through his doctorate, and I imagine will continue working for them afterward.

Paweł is a theoretical computer scientist, supervised by Mike Goodrich. The topics he included in his thesis were external-memory approximation of graph degeneracy, applications of list labeling in the visualization of dynamic graphs, and three-dimensional arc diagrams. For the third of these topics, he brought along some props, 3d prints of his graph visualizations, which I think make the graph structure much clearer than their 2d projections. He has also done some interesting work with Goodrich (not part of his thesis) on making parametric search practical, and very recently published another paper with me and others on cuckoo hashing on storage devices with limited rewrite capacity. After he finishes he will be joining navigation-system company TomTom in Berlin.

Congratulations, both of you!
 
 
0xDE
18 May 2014 @ 08:09 pm


Despite the name, it's not a university facility; it's a nearby mall with a nice Cuban restaurant in it. The stripy building is also a restaurant, but not one I've tried.
 
 
0xDE
11 May 2014 @ 03:07 pm
Here's a graph drawing problem I don't know how to solve: find the smallest 3-regular graph that is not 1-planar.

Read more...Collapse )
 
 
0xDE
09 May 2014 @ 10:46 pm
Today, Joe Simons (a joint advisee of Mike Goodrich and me) passed his thesis defense. Most of my own research with Joe has been on graph drawing, but his dissertation concerned several results on different models of time in dynamic geometric data structures, including the retroactive model (in which updates you make to past versions of the timeline have effects that propagate through other more recent updates), the windowed model (in which you have to aggregate the events that happened within a query window of time into a larger structure), and the local-update model (in which objects can move, but only proportionally to their size). Joe has accepted a position at Google starting this summer.
 
 
0xDE
08 May 2014 @ 11:57 pm
Via the Process Algebra Diary, I learned of a recent paper by Andreas Björklund and Thore Husfeldt, Shortest Two Disjoint Paths in Polynomial Time, which just won the Track A best paper award at ICALP. It looks like a very interesting paper; I can see why it won the award.

Here's the problem it solves: you're given a graph with two pairs of terminals s1t1 and s2t2. The goal is to find disjoint paths connecting the two pairs of terminals with minimum total cost. It almost sounds like the problem solved by Suurballe's algorithm, but that one allows either s to be connected to either t, while here we have to connect the correct pairs. The specific version of this problem they solve is for undirected and unweighted graphs, with disjointness meaning either that the paths share no vertices or that they can share vertices but not edges. The unweighted part could easily be modified to paths weighted by small integers. Directed or real-weighted versions would also be natural but I don't know what's known about them and I don't think this paper's ideas are likely to work for them.

Read more...Collapse )
 
 
0xDE
27 April 2014 @ 10:22 pm
I found this parachute rat in Costa Mesa today. I have no idea whether it's authentic — the lack of detail kind of suggests it isn't, but given the history of the artist in question, how meaningful is authenticity anyway?



Not coincidentally, but perhaps ironically given the subject matter, almost exactly a year ago I recommended a Korean time travel movie, Young Gun In The Time, which sadly still seems very difficult to find. This year's time travel movie recommendation is for an Australian romance, The Infinite Man. Tightly plotted, quite stage-play-like in its very sparse cast and setting, darkly funny, and in some ways reminiscent of Rashomon in the way it keeps bringing in unexpectedly different viewpoints to the same repeated scenes. I enjoyed it. There's still still another chance to see it this coming Wednesday, if you're local, interested, and lacking your own time machine.
 
 
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 )