Not Elsevier, this time. The rumor is that SAGE Publications, the corporate publisher of the journal Political Theory, have bypassed the journal's editorial board and unilaterally imposed a new editor. As one commenter (6/17 6:44 on the first thread below) states, "The idea that the editorship of the journal is to be determined directly by them, apparently with no formal consultation with members of the existing editorial community, is like the idea of a faculty search being run by a couple of corporate honchos from a University's Board of Trustees, without consultation with current members of the faculty of the relevant department."

See here, here, and here for discussion, but so far (despite a signed statement by one of the editorial board members) there's a lot more heat than light.

The FOCS accepted papers (with abstracts) have been posted. Since not every conference is doing this, I think it bears repeating that the addition of abstracts to these lists is a very welcome innovation of recent years.

And while I'm making a short link-only post, an amusing photo gallery that I was pointed to recently: the Russian solution to the art-gallery problem.

With all my traveling, I'd become delinquent at processing my photos, but I've caught up again (it made it easier that I edited the sets down to half a dozen photos each):

A school concert in which my son played viola, held at an auditorium at the local Lutheran college.

My recent trip to the Netherlands consisting of photos from the sculpture garden at the Kröller-Müller museum, a hike through Zuid-Kennemerland National Park, and the view from Marc van Kreveld and Bettina Speckmann's apartment.

Montpellier, France including a dinner with some other WG participants.

I just returned from Montpellier, France, where I was invited to speak at WG 2009, the 35th International Workshop on Graph-Theoretic Concepts in Computer Science.

This was my first trip to France, and Montpellier was a very charming place to visit. It is in the south, and though not quite on the Mediterranean itself it has a very Mediterranean feeling. The conference organizers put together an interesting and educational excursion for us in which we learned some of the local history by visiting three local landmarks (the opera house, an old pharmacy, and the top of the gateway arch) and drinking a different wine in each. We learned that Montpellier is a new city for France, being only a little over 1000 years old, but it is home to one of the oldest medical schools in Europe. It's on the old pilgrim trail from Rome to Compostela, markers for which run through the town, and although the language is no longer spoken in the area there are several inscriptions for tourists written in Occitan. The nearby mountains were a refuge for the Cathars when they were persecuted by the Catholics, and there are many open squares in the city due to the monasteries and other buildings that were torn down in the French revolution. My hotel was on one side of the old quarter, now mostly a shopping district, and the conference was in an old movie theater on the other side of the quarter, so I had a very pleasant walk every day to the conference (only getting lost twice), and my bad high-school French was enough to get by with the people who didn't or wouldn't speak English (rather more of them than I've encountered in other parts of Europe).

The conference itself is about graph algorithms, both for problems on arbitrary graphs and (a larger fraction of the papers) for important special classes of graphs. There were too many interesting talks to describe them all in detail, so let me just mention a few.

( Read more... )

All in all, a good conference, and one I would attend much more regularly if only it weren't so far away.

Via Michael Nielsen: Don't Ask, Don't Tell: Rights Retention for Scholarly Articles. My mother, a poet, thinks it very strange when she hears about the system of scientific publishing in which we give away the copyrights for all our papers. In poetry, the authors retain their copyrights, and give permission to publishers to publish their poems; the same is true in fiction writing. The system works without problems: it doesn't prevent publishers from going after people who illicitly copy their works, and it doesn't prevent them from getting exclusive publication rights to the works in question. So what, exactly, do we gain by giving away our copyrights? What we lose is the right to distribute our own works online for free; but as this Harvard Law blog post observes, many of us do that anyway, hoping that the publishers won't demand that we take them down again or sue us for noncompliance with their contracts. And mostly it works, but there's always that risk...

Fortunately, there is a solution: free online journals. The Journal of Graph Algorithms and Applications and the new Journal of Computational Geometry both are free as in free beer (no cost to access the papers, no publication fees) but also free in the sense that authors retain copyright and grant the publisher a license to print the paper. Therefore, I am happy to echo Suresh and Ernie Jeff and announce that JoCG is now open for business and accepting submissions.

One question I had with the new journal was, if it's online-only, how permanent are its archives? If whoever's running the journal gets hit by a bus, what happens to all the old papers? In today's business climate one should wonder about that for commercial journals too, I suppose. JGAA has been handling the issue by collecting its old issues into printed volumes, but as I understand it that arrangement has run into difficulties, so I was curious to hear what JoCG intended. Anyway, the answer is that they're using the Open Journal Systems software and LOCKSS data security model, in which university libraries maintain local copies of open content in order to assure its permanence. So I am greatly reassured on that front.

Therefore, as Samir exhorts us, get those SoCG papers into a journal. And now that we finally have a noncommercial alternative to DCG, CGTA, and IJCGA, let's support it by sending our papers there.

I just returned from a pleasant post-SoCG visit to Bettina Speckmann in the Netherlands. While there, she presented me with a copy of Metroville, a puzzle based on confluent drawing. (Image below stolen from the manufacturer's web site.)



Metroville consists of a game board with nine rotating pieces on it, each containing a section of train track with turns and junctions. The pieces can be permuted to form eight different "cities", and for each city there are eight puzzles, in which one must rotate the pieces so that the resulting configuration of track can allow a train to pass through a given sequence of cities in order without reversals.

I haven't worked out the details, but I'm pretty sure that larger versions of the game would be NP-complete (that is, it should be NP-complete to test, for a fixed city, whether there exists a set of rotations that allows a given train route to work) by a reduction from 3-SAT very similar to the one in my Phutball paper in which the train zigzags horizontally across the board through tracks representing variables and then zigzags again vertically through tracks representing clauses.

Regardless, it's a fun puzzle. Thanks, Bettina!

Also, slides from Elena Mumford's talk on area-universal cartograms (my SoCG paper with Bettina, Elena, and Bettina's student Kevin Verbeek) are now online.

The 25th ACM Symposium on Computational Geometry just finished yesterday. Suresh has already reported on the pre-conference historical review of computational geometry, but I thought I'd mention a few highlights of the conference itself.

( Read more... )

All in all, a good conference.

Life without Death is a cellular automaton with the same rule for creating new live cells as Conway's Game of Life, but in which no live cell ever dies. Despite the inability to create oscillators or spaceships (both of which require some cells to die sometimes) it has interesting dynamics due to the existence of ladders, patterns that grow at speed c/3 (that is, one unit of growth for every three time steps of the cellular automaton). Typical random seeds end up with from one to four chaotic regions spreading diagonally from the starting region, spewing ladders on both sides of them so that one ends up with a pattern in which the four quarters of the pattern (as split on roughly diagonal lines) are striped by axis-parallel ladders, separated by the chaotic regions. The chaotic regions separating the striped quarters tend to grow wider, but slowly as the pattern grows, and the boundary of the chaotic regions keeps pace with the ladders (probably in a self-limiting way: there is a pattern that grows at speed 2c/3 along the side of a ladder and then erupts in chaos at the tip, so if the chaotic growth regions ever fell too far behind they would catch up using this mechanism).

Patterns of this type can be simulated to hundreds of thousands of time steps using the Hashlife algorithm embedded into Golly.

But as it turns out there is another ladder, one that can grow more quickly (the text below is a pattern format that can be copied and pasted into Golly):

x = 26, y = 15, rule = B3/S012345678
obobobobobobobobobobo$23o$3ob3ob3ob3ob3ob3o$26o$26o$ob3ob3ob3ob3ob3ob
3o$3ob3ob3ob3ob3ob3obo$25o$3ob3ob3ob3ob3ob3obo$ob3ob3ob3ob3ob3ob3o$26o
$26o$3ob3ob3ob3ob3ob3o$23o$obobobobobobobobobobo!

Rather than growing at speed c/3, it grows at speed 4c/9. I've only seen this once out of many chaotic starting seeds, but if it happens once it should happen more than once. My suspicion is that most chaotic patterns should have a shape that eventually comes to be dominated by these faster ladders, but that even hundreds of thousands of steps isn't enough to see this domination.

ETA: animated gif by Simpsons contributor, who set this all off by starting a Wikipedia article on LwoD.

ETA2, 6/13: Already discovered in October 2000 by Dean Hickerson, who also found ladders of speeds 4c/10 and 4c/13. Dean's patterns: ( Read more... )

Boing Boing is showing a great information visualization concerning a case in which a college president has been accused of plagiarising his Ph.D. thesis, here. It consists of nothing more sophisticated than a yellow highlighter and a grid of thumbnail images of pages, but I think it conveys the message very effectively.

Someone recently added this new Wikipedia article on the fixed-radius near-neighbor search problem. I cleaned it up a little (it obviously needs a lot more work); in the process of the cleanup I changed the definition of the problem to better match the one in the Bentley reference. But before I got to it, the definition was that one should report all pairs with distance at most Δ in a given point set.

It occurred to me that the all-pairs fixed radius problem of the original version of the article has a simple solution with time linear in the input and output size (for any fixed dimension, assuming constant time integer truncation and hash table operations): use a hash table to group the points into cubical buckets with side length Δ, and for each point look at all potential neighbors in adjacent buckets. If some bucket contains many points, you might spend a lot of time examining pairs of points that are too far apart, but in that case there are many nearby close pairs against which the time can be charged: both the time and the number of reported pairs are proportional to the sum of the square of the bucket sizes.

This must have been known, probably in the 1960s or 1970s; it's a close relative of several linear-time randomized bucketing closest-pair algorithms, but even simpler. Bentley's 1975 survey mentions this sort of approach to nearest neighbor problems under the heading of "cell techniques", but without the hashing, without any analysis, and with a claim that these techniques require uniformly distributed points. Anyone know a reference for the linear time analysis?

In contrast, by the way, there can be no linear-time bucketing algorithm for finding the nearest neighbor of every point unless one is using a model of computation that can sort in linear time. The reason is that, if one can find all nearest neighbors, one can use something like Borůvka's algorithm to sort in one dimension: the nearest neighbor graph forms a set of non-overlapping paths, and one may replace each path by a single representative point and continue recursively.

This looks very promising, as does this.

*starts thinking about which of my computational geometry papers are in need of journal versions*

My Ph.D. student Kevin Wortman passed his thesis defense this morning, and is now (or will be when they hold the graduation ceremony in a week) Dr. Wortman.

Kevin (not to be confused with my other recent co-authors Kevin and Kevin, nor with the Utah mathematician Kevin Wortman) has been working with me since 2005, when we had a paper in SoCG on minimum dilation stars, or, less formally, the problem of selecting an airline hub that minimizes the maximum ratio between the route length between two cities through the hub and the straight-line distance. Since then, we've written more papers about fast approximations to the minimum dilation star problem, and minimum dilation stars for metric spaces (to appear at WADS), both of which became parts of Kevin's thesis. The minimum dilation star has led to the definition of a new triangle center, and an interpretation of dilation as a smoothed distance function is a key component of another paper with Kevin on generalized Voronoi diagrams. Kevin's graph drawing algorithms also formed the basis of the somewhat monstrous graph drawing below, a more legible version of the drawings in this post that I needed for my recent work on squaregraphs.

Kevin has a job offer from California State University, Fullerton (also in Orange County, but with heavier teaching loads and less of the heavy emphasis on research that the University of California has) and will start there in August. Landing a job like that in the current economic climate is not easy (we just received word of a hard hiring freeze on our own campus) but well deserved.

Congratulations, Kevin!

I have another preprint on the arXiv: “Combinatorics and geometry of finite and infinite squaregraphs” (arXiv:0905.4537), with Hans-Jürgen Bandelt and Victor Chepoi. It's a long one, 46 pages, and as the title says is about the properties of squaregraphs, planar graphs in which all the interior faces are quadrilaterals and all the interior vertices have degree at least four.

( Read more... )

I just wrote a major expansion of the Wikipedia article on the Bentley–Ottmann algorithm, the plane sweep algorithm for listing all crossings among a set of line segments. As usual, feedback would be very welcome; I already know that it could still use illustrations, and the article on the closely related Shamos–Hoey algorithm for detecting a single crossing is completely missing.

One surprise for me as I was researching this: Chazelle and Edelsbrunner, in their 1992 JACM paper on deterministic O(n log n + k) algorithms for constructing arrangements of line segments, leave as an open problem whether it is possible to list all crossings deterministically in the same O(n log n + k) time bound as their algorithm but with the O(n) space bound of Bentley–Ottmann, rather than the larger O(n + k) required for storing the whole arrangement in memory. I had thought that this was one of the problems solved by topological sweeping, but if so I don't know what the right reference is: the original Edelsbrunner–Guibas topological sweeping paper appears to be only for line arrangements, and the Asano–Guibas–Tokuyama SoCG '91 paper extends the topological sweeping method to the intersection of a line arrangement with a convex region of the plane, but not to arbitrary line segment arrangements. Can this really still be open?

ETA: Seems not to be open; see comments.

A reminder: the Graph Drawing Symposium submission deadline is approaching. Get your graph drawing submissions ready!

We recently changed the submission deadline, from May 31 to June 3, to articulate better with some other conference deadlines. Unlike previous years' extensions we've tried to make this change sufficiently early that it will also be useful for providing extra time to write new submissions.

VanderZee et al have solved an open problem in mesh generation from one of my earlier papers (with Sullivan and Üngör): is there a partition of a cube into tetrahedra, meeting triangle-to-triangle and edge-to-edge, with the property that ell the dihedral angles of every tetrahedron are acute? In our earlier work, we were only able to show the existence of acute triangulations of this type for infinite slabs, but the new paper shows that they do exist for cubes. The triangulation they find is well-behaved in other ways as well: the angles are bounded well away from right angles, and every tetrahedron contains its circumcenter.

This work raises the possibility that every polyhedron has an acute triangulation, but that remains an open problem still.

This afternoon there was a minor aftershock of Sunday's LA earthquake, and I noticed that the time on the USGS earthquake report was pretty much the same as when I felt it several tens of miles away. So I became curious: how fast do earthquakes travel, anyway?

This seemed like a good test case for Wolfram Alpha, a fancy new search engine from the makers of Mathematica, so I thought I'd try it. But "earthquake speed" as a query led it to think I was asking about two action movies with those titles, "how fast does an earthquake travel?" just confused it, and substituting "seismic wave" for earthquake at least avoided the movie misinterpretation but didn't get me any better results. "Seismic wave" alone as a query gave the results "Seismology: Additional functionality for this topic is under development... Leave your email address to be notified when it is ready." And I still didn't find out what I had set out to.

Finally, I gave up, went to the Google search box in my browser's toolbar, and typed the same query I'd started with, "earthquake speed". The first hit was exactly on-topic, and the snippet Google displayed with the hit showed that it was on-topic. The answer: it varies, but for the roughly 56 km between the epicenter and my location it should have taken between 4 seconds (for the fastest P waves) and 16 seconds (for the slowest S waves).

Combined with Wolfram Alpha's Babylonian arithmetic fiasco, this does not fill me with a lot of confidence in their service...

Short conclusion: I still feel lucky.

Apparently any email containing a URL to this journal (http://11011110.livejournal.com), even as plain text, is being interpreted as "URL Obfuscation" by the AT&T Research email servers, and permanently blocked. I haven't done enough experiments to tell whether they don't like any URLs, or just not mine, but my guess is that it has something to do with the purely-numeric domain name component.

It's a pretty obvious observation that the graphic conventions we use when illustrating mathematical objects can have a lot to do with how we think of them. The standard way the computer science textbooks draw trees is like a biological tree, but upside-down, with the root at the top and the leaves at the bottom:



When we view a tree in this way, the traversal order given by breadth-first search forms a geometric pattern that scans left-to-right across the vertices in a single level of the tree (conventionally, these vertices lie along a horizontal line), then the next level, and so on, much as one reads English text left-to-right and line-by-line. And this level-by-level ordering can be useful for conveying the idea that breadth-first search sorts vertices by their distances from the root.

But the breadth-first search algorithm itself, as it is usually described, does not progress level-by-level.( Read more... )

In the revisions of one of my papers, I needed an illustration of the graph shown below, which comes from an NP-completeness reduction. This is a confluent drawing: two vertices are connected by an edge whenever there is a smooth path between them. (The paths are allowed to self-intersect, so for instance all 30 outer vertices form a clique.)



I think it's a great illustration of the power of confluent graph drawing: the graph has 37 vertices, 536 edges, and an average degree of nearly 29, but despite being so dense the graph has a lot of structure and the drawing makes the structure apparent.