Can a triangle up to isometry shatter seven points?

96 Views Asked by At

From Wikipedia:

The class [of sets] $C$ shatters the set $A$ if for each subset $a$ of $A$, there is some element $c \in C$ such that $a = c\cap A$.

In other words, $C$ shatters $A$ if for every subset $S\subset A$, it's possible to find a set $c\in C$ which covers the points in $S$ but none of the points in $A\setminus S$. For instance, if $C$ is the set of closed half-planes, then $C$ shatters any non-colinear set of three points, but does not shatter a unit square, because it isn't possible to cover one diagonal while omitting the other.

Given a triangle $T$, let $C$ be the set of all isometric copies of $T$ - all translations, rotations, and reflections of $T$ in the plane, not permitting scaling.

What is the maximum size of a set $A$ such that for some triangle $T$, $C(T)$ shatters $A$?

It's possible to attain $|A|=6$ by taking $A$ to be the vertices of a regular hexagon of unit side length and $T$ to be an isosceles triangle with side lengths $(2.8,4.48797,4.48797)$. Below are diagrams of every configuration up to dihedral symmetry:

enter image description here

On the other hand, it's impossible to have $|A|=8$. Note that every point of $A$ must lie on a vertex of its convex hull, or else taking $S$ to be the convex hull would prove impossible (since a triangle is convex). So $A$ must be the vertices of a convex polygon. But then take $S$ to be an alternating set of four points around the perimeter of $A$: this forces a side of our triangle to lie in four different places, none of which are compatible, which is a contradiction since we only have three sides available. (To see that the side restrictions are incompatible, observe that the permissible oriented angles enforced by each region are disjoint intervals.)

This only leaves the case $|A|=7$. Is it possible?

I've tried some approaches where $A$ is a regular heptagon, and wasn't able to find something that worked, but I'm not confident I've ruled out even that case (I think an isosceles $T$ at least is not possible with such an $A$).

1

There are 1 best solutions below

2
On BEST ANSWER

This is indeed possible. The points $(0.95,0.4)$, $(0.63,0.13)$, $(0.37,0.12)$, $(0.25,0.44)$, $(0.35,0.83)$, $(0.46,0.96)$ and $(0.91,0.76)$ are shattered by copies of a triangle with squared side lengths $3.637$, $3.1492$ and $0.8194$.

Here are $18$ diagrams that exhibit all the subsets. The three green points lie on the perimeter, and the triangle can be infinitesimally disturbed so as to contain any of the $8$ combinations of these three points. At least $16$ such diagrams are required to cover all $128$ subsets, but I didn’t find a solution with less than $18$ diagrams.

shattering shattering shattering shattering shattering shattering shattering shattering shattering shattering shattering shattering shattering shattering shattering shattering shattering shattering

Here’s the Java code I used to find this configuration. It generates random convex heptagons and triangles, finds all isometries that make two points lie on one side of the triangle and a third point on a second side, checks whether all subsets are covered in this way and then uses simulated annealing to find a minimal subset of the resulting diagrams that covers all subsets. Note that another option would be to put one point on each side of the triangle – that would yield more diagrams to choose from and thus might allow a cover with $17$ or $16$ diagrams, but that potential slight improvement didn’t seem worth the extra coding effort.

I let a version of the code that uses a regular heptagon run for several hours, which is several orders of magnitude more than was needed to find a solution with a random heptagon, so it seems that there’s no solution with a regular heptagon.