?

Log in

0xDE
13 October 2016 @ 04:46 pm

Draw an infinite tree according to the following rules:

  • Each tree node is labeled 1 or 2, and has a number of children equal to its label.
  • If the nodes are placed into their breadth-first search ordering, then two consecutive nodes have the same label if and only if they have the same parent.

There are two choices for the root label, but the trees they produce are almost the same as each other, so let's say the root is labeled 2, giving the tree shown below together with its spiraling breadth first search order. (If the root were labeled 1, the only difference would be to add one more node labeled 1 above the node that is the root in the drawing.)

Then the breadth-first sequence of labels that we obtain is exactly the Kolakoski sequence, starting from its third term. The Kolakoski sequence begins 1,2,2,1,1,2,1,2,2,1,2,2... and has the property that it equals the sequence of run-lengths in itself: the numbers 1, 2, 2, etc. are exactly the numbers of consecutive 1's, 2's, 1's, etc. in the sequence. Our tree is defined in such a way that each run of consecutive equal labels comes from the same parent, so the run-lengths of the sequence equal the numbers of children of the nodes, which equal the labels of the nodes, which define the sequence itself.

Read more...Collapse )

ETA: See next post for an alternative algorithm that avoids the recursion.

 
 
0xDE
While fixing up the Wikipedia article on the constant-space streaming majority algorithm of Boyer and Moore I ran across a stackoverflow question complaining about some sloppy analysis that I had already removed from the Wikipedia article. As a quick reminder, the algorithm stores one element from its input sequence, uses comparisons of that element with input values to decide whether to increment or decrement a counter, and uses comparisons of the counter with zero to decide when to replace the stored element.

Read more...Collapse )
 
 
 
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 )