?

Log in

0xDE
16 September 2016 @ 04:55 pm
I have another new arXiv preprint: "Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection", arXiv:1609.04512, with Juan Besa, Will Devanny, and Mike Goodrich. The same paper also appeared at ATMOS 2016; the two versions differ only in formatting and their theorem numbering scheme.

Read more...Collapse )
 
 
 
0xDE
07 September 2016 @ 12:17 am
It's pretty well known that a finite lattice has order dimension ≤ 2 if and only if its Hasse diagram is an st-planar graph (below left), and every transitively reduced st-planar graph defines a 2-dimensional lattice in this way. The reference I know of for this is Platt, "Planar lattices and planar graphs", J. Comb. Th. 1976. And I don't know who first observed that the 2-dimensional finite distributive lattices are the ones that can be drawn as grid graphs (below right) but my guess would be Garrett Birkhoff.



My own paper "Upright-quad drawing of st-planar learning spaces" described an analogous geometric representation for antimatroids (which in this context can be seen as another special type of lattice). So a recent CS-theory stack-exchange question about planar modular graphs got me wondering: what do the graphs of 2-dimensional modular lattices (a subclass of the planar modular graphs) look like?

Read more...Collapse )
 
 
 
0xDE
18 August 2016 @ 06:33 pm
Suppose we play the following game. We place a bunch of hexagonal game board tiles on a table, edge-to-edge, to form our playing field. On the field, we place two game pieces, a cop (blue) and a robber (red). The cop and robber take turns, either moving to an adjacent hex or passing (staying put). The cop wins if he can end a turn on the same hex as the robber. The robber wins by evading the cop forever. Who has the advantage?



Read more...Collapse )
 
 
 
0xDE
07 August 2016 @ 04:37 pm
One of the talks at CCCG was by Ahmad Biniaz, on red-blue-purple spanning graphs: given a partition of a point set into red, blue, and purple points, find a minimum-weight graph such that the red-purple and blue-purple subsets induce connected subgraphs. It can be solved by matroid intersection, but this is slow and Biniaz talked about a faster special case. Anyway, in his talk, Ahmad mentioned a different colored spanning problem: find a minimum spanning tree of the complete bipartite geometric graph determined by a set of red and blue points in the Euclidean plane (with no purple this time). He noted that bichromatic closest pairs can be used to solve it in time O(n log8 n), and asked whether a faster algorithm is possible. The illustration below gives an example of this problem and its solution.



Read more...Collapse )
 
 
0xDE
05 August 2016 @ 05:14 pm
This week I've been in Vancouver for the Canadian Conference on Computational Geometry, where I spoke about radius-sum optimization. This seemed like a good occasion to post a pointer to the slides from my recent conference talks (and to go back through the talks to make sure their slides were all online), so here they are:
 
 
 
 
0xDE
Suppose you have an array of n real numbers (or other totally ordered values that you can compare but not treat as small integers). You want to answer queries that specify a contiguous subarray and return the sorted sequence of values within that subarray. Without any preprocessing you could query a subarray of length k in time O(k log k), by pulling out the subarray and then comparison sorting it. With preprocessing, how much better can we do?

Read more...Collapse )
 
 
0xDE
I have another new paper out on arXiv: "Maximizing the Sum of Radii of Disjoint Balls or Disks", arXiv:1607.02184, to appear at CCCG. The problem solved by the paper is, as the title says, to find a set of disks in the plane (or balls in a metric space), with given centers, that do not overlap each other and have as large a sum of radii as possible. There's some weak motivation in terms of map labeling, but really it's an exercise in how LP duality and sparse graph theory can be used to find efficient combinatorial algorithms for problems that can be solved numerically and less efficiently by linear programming. In fact as I was writing it I half-expected the metric space part to show up as an exercise in a book on related topics, such as Vazirani's book on primal-dual approximation algorithms. Maybe it is and I just didn't find the reference; if so please tell me.

Read more...Collapse )
 
 
0xDE
04 July 2016 @ 06:11 pm
Here's an update to the streaming integer point puzzle that I posted yesterday. Recall that the puzzle was to generate all the integer points in the plane, in constant amortized time per point, using as little space as possible. In the post, I gave a solution whose space is proportional to the square root of the number of points generated so far. In the comments to my G+ link to the post, Sariel Har-Peled suggested an improvement, but without much detail. So, here is some detail for Sariel's idea.

Read more...Collapse )
 
 
0xDE
Here's a puzzle in streaming algorithms: suppose you want to generate a stream of all the (infinitely many) integer points (x,y) in the plane, in sorted order by their Euclidean distance from the origin. How little space do you need?

Read more...Collapse )
 
 
0xDE
02 July 2016 @ 10:42 am

Here are some of my photos from the SWAT excursion to the Reykjanes peninsula, and of some of the participants. Iceland (even this small part of it) was easily as scenic as I had been led to believe.





( The rest of the photos )

 
 
0xDE
30 June 2016 @ 10:35 pm
I'm getting the hard-to-quantify but persistent feeling that G+ is getting quieter lately...too much of the actual content has moved elsewhere, maybe, and I'm seeing more of the filler. Wouldn't be surprised if Google pulls the plug soon, like they have on other projects. But for now here's my filler for the last couple of weeks.
 
 
0xDE
28 June 2016 @ 09:22 pm
Here's the first of two batches of photos from my recent visit to Iceland. This set is from before the conference, when I had most of a day free to wander around Reykjavik. It's mostly of street art from the touristy shopping area where my hotel was located, and graffiti from some rougher looking areas nearby. This shot was the first I had a chance to take, of a building across the street from my hotel:



( More photos )
 
 
0xDE
25 June 2016 @ 09:04 am
I'm now making my way back from Iceland, where I attended the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Rather than providing a run-down of the talks and results I found interesting (you can choose your own from the conference proceedngs, this year provided as open-access through LIPIcs), I thought it might be more fun to mention a few open problems that people mentioned along the way and that caught my attention.

Read more...Collapse )
 
 
0xDE
19 June 2016 @ 06:02 pm
I've been slow processing this but the arrival of the official shots reminded me: this is from my daughter's graduation a month ago from Lesley (with a B.F.A. in photography).



Sara tells me she likes the other shot better, though.