One of our students made a seminar presentation this week on the problem of covering a given set of \(n\) points by two scaled and translated copies of a given convex \(k\)-gon, minimizing the scale factor, based on a 2016 conference paper on the problem published by someone else. The presentation was good but the paper turns out to be wrong in several ways. I think it should not be difficult to find the paper if you look, but I’m avoiding naming it here: it’s uncited, so it hasn’t done much damage to the literature, its author’s other papers are not as far as I know problematic, the author appears to want to forget the paper (there was no journal version and it is not included in their online publication list), and I want to focus on the geometric nature of the mistakes rather than on pointing fingers.

The algorithm of the paper starts by (correctly) computing the optimal cover of the given points by a single copy of the polygon. This is a low-dimensional linear program, but one with \(O(nk)\) constraints, one for each pair of a side of the polygon and an input point to be covered. The paper makes the observation that the only pairs that matter are the ones that match each side to the extreme point in a perpendicular direction, and it uses a nice divide-and-conquer method to find these extreme points in time \(O(n\log k)\), which turns out to be the bottleneck of the algorithm.

It then tries to use this one-copy cover to speed up the two-copy cover, and this is where things go wrong. It claims that if the one-copy cover has five or more of its sides touched by input points, then the optimal two-copy cover has the same scale factor: there are so many touching points that three or more of them would all have to be in the same copy of the two-copy cover, and would force it to have the same size as the one-copy cover. This is false.

Even when a regular hexagon is touched on six sides by the points that it covers, it may be possible to cover the same points by two smaller regular hexagons

It claims that, when four or fewer sides of the one-copy cover are touched by input points, then for the optimal two-copy cover, one of the two copies will be touched on two sides with the same slopes. If true this would greatly simplify the search for the optimal partition into two subsets and the optimal scale factor for that partition. But it is false: there exist instances where the slopes of sides touched on the two-copy cover are completely disjoint from the slopes touched on the one-copy cover.

Even when an octagon is touched on four sides by the points that it covers, the smallest two scaled and translated octagons that cover the same points may not be touched on any of the same sides

I think what is going on here is a more general phenomenon relating to linear programming, rather than to this specific geometric optimization problem. Suppose you have a linear program with \(k\) variables (here, three variables for the scale factor and translation vector of the single-copy cover), and to keep things simple let’s say that it has a unique optimal solution. That solution will be determined by a basis, a minimal subset of inequalities with the same solution. The basis inequalities become tight equalities rather than inequalities, and if you know which ones they are then you can just solve these \(k\) linear equations in the \(k\) unknowns. However, more than \(k\) inequalities may be tight, and there may be more than one basis. With some additional assumptions that are automatically satisfied here you can choose any \(k\)-tuple of tight inequalities, solve linear equations, and get the same solution. But that does not mean that every \(k\)-tuple of tight inequalities is a basis, and it does not mean that these tight inequalities stay tight for all subsets of the constraints.

Turning this idea back into geometry, in each of these figures, the inequalities come from pairs of a point and a polygon side. Each inequality states that its point must be contained in the halfspace bounded by its side, and it is tight when the point lies on the side. Any translated and scaled copy of a polygon is determined by points that touch any three of its sides. But forming a basis, for the problem of covering points with the smallest possible copy, is a stronger property. A set of three sides and (maybe fewer than three) touching points forms a basis only when the normal vectors to those sides do not span an angle less than \(\pi\).

For instance, for the hexagons of the first illustration, triples of consecutive sides have normal vectors that span only an angle of \(2\pi/3\), too small to form a basis. Other triples of sides have normal vectors that are more spread out and do form a basis. The blue one-copy hexagon containing all of the points is optimal, because all six of its sides are touched, and many triples of those touched sides are non-consecutive. But when we split the points into the two yellow hexagons, each yellow hexagon contains the points that touch only a consecutive triple of blue sides, not a basis. Because they are not a basis, those three points (and the other points that are grouped along with them) can be contained in a smaller hexagon than the blue one. (Exercise: find a basis for one of the yellow hexagons, showing that at least for this partition into two subsets the scale factor is optimal.)

(Discuss on Mastodon)