[seqfan] Re: How many squares can you make from n points in the plane?

[Benoît Jubin]

Is there an OEIS entry for the related sequence restricted to
axis-parallel squares ?  That sequence is Theta(n^(3/2)) (whereas
A051602 is Theta(n^2)), and it seems likely that an asymptotically
optimal configuration is the full grid [1, \sqrt(n)]^2.  Computations
are easier, and a proof that for most values of n, there exist optimal
n-configurations which are grid configurations may be easier in that
case.  A starting article, which gives algorithms to compute the
sequence, is

Kreveld, van, M. J., & Berg, de, M. T. (1989). Finding squares and
rectangles in sets of points. (UniversiteitUtrecht. UU-CS, Department
of Computer Science; Vol. 8910). Utrecht University.
https://pure.tue.nl/ws/portalfiles/portal/4288742/369233.pdf

Any volunteer to compute values and add that entry ?

Benoît

On Fri, Oct 8, 2021 at 2:05 PM Benoît Jubin <benoit.jubin at gmail.com> wrote:
>
> Hi Sascha,
> Unless I misunderstood (and it's quite easy to misunderstand your
> style), this is no proof.  For instance, where are you using that the
> configuration is optimal ?
>
> I tried a bit to prove that a = b but found flaws in all my attempts.
> This looks like a hard result, and one has to consider the whole
> configuration: local arguments cannot suffice.
>
> Benoît
>
> On Fri, Oct 8, 2021 at 11:55 AM Kurz, Sascha
> <Sascha.Kurz at uni-bayreuth.de> wrote:
> >
> > Earlier Hugo wrote
> > : Are we ready to conjecture that all maximal arrangements can be
> > : generated by such [2-] extensions?  If we are, it's worth noting that this
> > : also trivially implies a(n) = b(n).
> >
> >
> > I would bet on this conjecture too.  However, a(n)=b(n), i.e. assuming
> >
> > that  all points are located on the integer grid, can be shown more directly.
> >
> > To this end let the n points be represented by real-valued coordinates
> >
> > (x_i,y_i) that we consider as variables. Each square j can be represented by
> >
> > two additional real-value variables (u_j,v_j) and generates 6 linear equations.
> >
> > To ease the notation, assume that the clockwise ordering of the vertices of the
> >
> > square is (x_1,y_1), (x_2,y_2), (x_3,y_3), (x_4,y_4). With this, the equations
> >
> > given by the square are
> >
> > x_2 = x_1 + u_j
> >
> > y_2 = y_1 + v_j
> >
> > x_3 = x_2 + v_j
> >
> > y_3 = y_2 - u_j
> >
> > x_4 = x_3 - u_j
> >
> > y_4 = y_3 + v_j
> > (The intuition is to consider (u_j,v_j) as the vector from (x_1,y_1) to (x_2,y_2) and
> > to consider its perpendicular versions, pointing into the chosen orientation).
> >
> > Starting from an arbitrary point set this equation system has a solution, that may
> > contain irrational components, so that the solution space is a non-empty affine space.
> > By small perturbation of the entire space we can assume that it contains a rational point,
> > which then gives rational values for all variables (since the coefficients of the equations are
> > all rational). The only technical issue are degenerations in terms of coinciding points or square
> > sides of length zero (u_j^2+v_j^2=0), which is a special case of the former.
> > Starting from an existing point set initially, no such degenerations occur. Choosing the
> > perturbation sufficiently small, none will occur. Finally, by scaling, we reach a representation
> > on the integer grid.
> >
> > So, in principal, we can check each hypothetical combinatorial description of the incidences between
> > (oriented) squares and points whether it can be realized in the Euclidean plane. (Degenerations
> > that cannot be resolved by small pertubations can be characterized easily.) We may also formulate
> > an 3-extension step (if we deal with solution spaces of linear equation systems instead of exact coordinates)
> > and perform an exhaustive search for the optimal configurations.
> >
> > The above equations smell a bit like a 2-dimensional sumset probem. Any experts on the list?
> >
> > Best regards,
> > Sascha
> >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/