Log in

07 December 2016 @ 09:11 pm
My latest arXiv preprint is "Covering many points with a small-area box", arXiv:1612.02149, with de Berg, Cabello, Cheong, and Knauer. It is about finding an axis-parallel rectangle that covers k out of n points in the plane and has as small area as possible. Here, both k and n are variables, but k is expected to be significantly smaller than n. So, in finding a fast algorithm, the goal is first to minimize the exponent of n in the time bound, and only after that to minimize the dependence on k. We achieve a bound of O(nk2log n). There are also some related algorithms for approximating the dual problem where you are given a fixed area and want to maximize the number of points that are covered.

The result has a bit of a curious history. A group of us worked on it, and came up with the best algorithms we could, thinking it was a new and unsolved problem. Then, we did a more careful literature search and found that it was actually a known problem, and worse than that, that the time bounds we had achieved were all known or improved, so that we had no result. But then we looked again and discovered that the supposedly known bounds aren't actually true.

What happened was that there was a line of research (that I was part of) in the early 1990s on finding "small" subsets of a given number of points. A sequence of papers on this subtopic identified many different definitions of what it meant to be small (like having low circumradius, diameter, etc) that could all be solved by similar algorithms. These algorithms worked by covering the input by clusters of O(k) points, one of which could be guaranteed to include the optimal solution, and then worked separately within each cluster. A simple version of this is to choose O(k) nearest neighbors to each point and to use these n sets of near neighbors as the clusters; later refinements used fewer and easier-to-find clusters. The algorithms of this type varied by what they did inside the clusters, but this general method ensured that the dependence on n would be linear. And one of the problems solved using this approach was almost the same as the one in our new paper, but with axis-parallel rectangle perimeter in place of rectangle area.

Later, another paper studied the problem of finding smallest rectangles covering k points, but with k assumed to be very close to n rather than much smaller than n, so that factors of k in the runtime are bad and factors of (n − k) are good. It solved both the minimum-perimeter and minimum-area problems for the large-k case. Of course, it quoted the past work on the minimum perimeter problem for small k, but it didn't make clear that this past work solved only the case of perimeter minimization and not area minimization. And so, other papers, quoting that one, started also saying that the minimum-area k-point rectangle problem (for the small-k case) had also already been solved.

It hadn't, but now it has.
24 November 2016 @ 01:59 pm
Happy Thanksgiving to all. Here's a photo from a walk I took this morning at the San Joaquin Wildlife Sanctuary.

The gallery has a few more.
20 November 2016 @ 03:32 pm
While looking something else up on OEIS I ran across a conjecture by Zhi-Wei Sun from September 2015 that every positive rational number has an Egyptian fraction representation in which every denominator is a practical number. The conjecture turns out to be true; here's a proof.

Read more...Collapse )
16 November 2016 @ 01:31 pm
I used the sieving algorithm for subtract-a-square to generate its P-positions (the ones you want to move to) in order to estimate how quickly this sequence of positions grows. Based on some assumptions that the sequence was basically random and on considerations involving the coupon collector problem, I was expecting its growth rate (the number of P-positions up to n) to be roughly O(sqrt n log n). But that seems to be inconsistent with the data. Instead (based on generating the first 350k or so of these numbers) it seems to be more like O(n0.69), a surprisingly high growth rate.

Read more...Collapse )
14 November 2016 @ 10:24 pm

The game of subtract-a-square is played by two players with a pile of coins. They take turns taking a square number of coins until none are left. The last player to move wins. So how can we play this game optimally and efficiently? As it turns out, there's some deep number theory lurking in the answer.

Read more...Collapse ) Update: See a later post for some experiments on the growth rate of this set.
08 November 2016 @ 09:24 pm
Most or all of the following seem destined to be gone, in the US and (for some) the world:

Climate change countermeasures and continued research.
A coordinated response to extreme climate events.
Regulation of carbon dioxide as a pollutant.
National parks and wildlife preserves.
Guaranteed health care.
State-level limits on how predatory the health care industry can be.
A recovering economy and continuing tech boom.
Internet neutrality.
The minimum wage.
Social security and medicare.
The Supreme Court.
Abortion rights and access to contraception.
Anti-discrimination laws and same-sex marriage.
The truth defense from libel.
No wholesale legal persecution of opposition parties.
Restrictions on gun ownership.
Religious freedom for anyone other than Christians.
Limits on how blatantly Christianity can be used as an excuse for bigotry.
Redistricting rules that prevent continued gerrymandering.
Anything resembling adequate polling places in poor and minority districts.
Universal voter registration.
Pressure to reduce sexual harassment and sexual assaults in our universities, or anywhere else.
Reduced or free college tuition for anyone.
Any hope of reining in the out-of-control racists in our police forces.
Farm workers, housecleaners, construction workers, food service workers, and all those other people who do the things nobody else wants to do.
The ability to bring in talented students and workers from other countries.
NATO and the free Baltic states.
Nuclear non-proliferation.
A president who wouldn't start a nuclear war based on a whim or personal slight.

Clinton could still pull this out, mathematically, but barring a miraculous turnaround in Wisconsin or Arizona there doesn't seem to be any remaining path to 270 electoral votes. And with the House and Senate in Republican hands and a free slot on the court there are no checks and balances left; the voters were the last line of defense.

Anyone in a nice safe part of the world looking for academic computer scientists? Canada? Iceland? New Zealand?
23 October 2016 @ 05:51 pm

In Conway's Game of Life, and other cellular automata with the same neighborhood structure, you can determine the values of the cells in any 2x × 2x square of cells from their values x steps earlier in a bigger 4x × 4x square. If we view this as a time-space diagram, with two of the dimensions as the spatial dimensions of the Life grid and the third dimension as time, we can view the bigger starting square and the smaller resulting square as the bottom and top of a sort of stepped pyramid formed by stacking concentric squares. The values of the cells in each layer of the pyramid are determined by the ones in the layer below. The squares shrink inward as they rise upward, because the other cells outside the pyramid need more information (outside the base of the pyramid) to determine their values. The image below shows this construction for x = 1, 2, and 4, with each time-space state of a cell represented as a cube.

Read more...Collapse )

After posting about a recursive generator for the Kolakoski sequence yesterday, I found the following alternative and non-recursive algorithm, which generates the same sequence in a linear number of bit operations with a logarithmic number of bits of storage.

def Kolakoski():
    x = y = -1
    while True:
        yield [2,1][x&1]
        f = y &~ (y+1)
        x ^= f
        y = (y+1) | (f & (x>>1))

Like the previous one, this can be understood as traversing an infinite tree. The tree is defined using essentially the same rules as before: two consecutive nodes on the same level of the tree have the same number of children if and only if they have the same parent. However, it extends infinitely upward rather than infinitely downward, with two children for each node on the leftmost path. Each level of the tree has the same sequence of degrees, which equals the Kolakoski sequence starting from its second position (the missing first position is why this starts at x = y = -1 rather than zero).

The algorithm traverses the bottom level of the tree in left-to-right order. As it does, the variable x maintains, in its binary representation, the numbers of children modulo 2 of the path of nodes extending infinitely upwards from the current leaf. All but finitely many (logarithmically many as a function of the position of the leaf) of these bits are zero, so (after the first step) x is a non-negative finite number with logarithmically many bits. The variable y, similarly, maintains a sequence of bits corresponding to the nodes on the same path that are 0 when the node is a left child of a degree-2 node and 1 otherwise. Again, finitely many of these bits are 1, so y is non-negative with logarithmically many bits. The bit manipulation tricks of the algorithm merely update these two variables to describe the next path in the traversal.

Update 10/16: Fast C++ implementation by Jörg Arndt

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.

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 )
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 )
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 )
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 )