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

Allan Wechsler acwacw at gmail.com
Sat Oct 2 15:42:01 CEST 2021 

I am pretty sure that if you have a bunch of points on a grid, any new
point that completes at least one square must also be on the grid. So if
there is anything to be gained by going off grid, it's subtle and involves
lots of new points, not just one.

On Sat, Oct 2, 2021 at 1:28 AM Neil Sloane <njasloane at gmail.com> wrote:

> well, I was thinking that the best new point might just possibly be at the
> vertex of an equilateral or isosc triangle!  and that would take us "off
> the grid"!
> Best regards
> Neil
>
> Neil J. A. Sloane, Chairman, OEIS Foundation.
> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
>
>
>
> On Sat, Oct 2, 2021 at 1:23 AM Allan Wechsler <acwacw at gmail.com> wrote:
>
> > I didn't think of the unconstrained version. Now that you suggest it,
> > though, I'm very curious to know: if you initialize with a gridded
> > collection of points, would the best new point ever be off the grid? If
> it
> > were, I think it has to have rational coordinates, and thus could be
> > captured in a new, finer grid.
> >
> > I am having trouble explaining my skepticism that the unconstrained
> version
> > adds any actual possibilities. And yet, in the superficially similar
> > problem of maximally-dense unit distance graphs (see
> > https://oeis.org/A186705), I think the ungridded problem definitely
> gives
> > denser solutions. Is there a sequence already for the gridded analog of
> > A186705?
> >
> > On Fri, Oct 1, 2021 at 10:54 PM Neil Sloane <njasloane at gmail.com> wrote:
> >
> > > Allan,  Good suggestion!  There are 2 versions, right?  New point has
> to
> > be
> > > a grid point, or, new point can be anywhere!
> > >
> > > Best regards
> > > Neil
> > >
> > > Neil J. A. Sloane, Chairman, OEIS Foundation.
> > > 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> > > Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway,
> NJ.
> > > Phone: 732 828 6098; home page: http://NeilSloane.com
> > > Email: njasloane at gmail.com
> > >
> > >
> > >
> > > On Fri, Oct 1, 2021 at 10:47 PM Allan Wechsler <acwacw at gmail.com>
> wrote:
> > >
> > > > Has anybody tried a greedy adjustment algorithm? Start with N
> > arbitrarily
> > > > chosen points, and then alternate removing the point that
> participates
> > in
> > > > the fewest squares with adding the point that would introduce the
> most
> > > > squares. There's no reason to think this would magically find a
> global
> > > > optimum, but the general structure of what it did converge on might
> be
> > > > enlightening.
> > > >
> > > > On Fri, Oct 1, 2021 at 6:42 PM Benoît Jubin <benoit.jubin at gmail.com>
> > > > wrote:
> > > >
> > > > > Thanks Alex. Since a(n) >= n^2/12 - O(n), circles are out.  Maybe
> try
> > > > > octagons which are intersections of two concentric squares rotated
> by
> > > > > pi/4 (so there are two side lengths) ?
> > > > >
> > > > > I'm not sure I understand your computation: for each point with
> > > > > coordinates (a,b) or (a+1/2, b+1/2) within the shape, you compute
> the
> > > > > number of squares which have it as center (both the horizontal ones
> > > > > and the slanted ones; this is easy to compute from the distance of
> > the
> > > > > center to the boundary of the shape).  For the cercle, this is
> > > > > espacially easy.  Is that it ?  In that case, the octagon are a bit
> > > > > more tedious (a few different cases to handle) but seems doable.
> > > > >
> > > > > Side note: Peter corrected me: in the example above, I obtain a(49)
> > >=
> > > > > 204.  Sascha found 205, so we may have to wait Monday to see his
> > > > > configurations.
> > > > >
> > > > > Benoît
> > > > > On Sat, Oct 2, 2021 at 12:28 AM Alex Meiburg <
> > timeroot.alex at gmail.com>
> > > > > wrote:
> > > > > >
> > > > > > I ran the computation for what happens if you take a circular
> > region
> > > of
> > > > > > points in a grid. It's fairly straightforward in the asymptotic
> > case,
> > > > > > because it all just comes down to computing (and integrating)
> > areas,
> > > > and
> > > > > we
> > > > > > don't have to actually worry about the integrality of points;
> and a
> > > > > result
> > > > > > it becomes rotationally invariant. It comes out to 3(1/16 -
> > 1/8pi)n^2
> > > > > > ~=  0.0681338 n^2  ~=  n^2 / 14.677, assuming I didn't make a
> > > mistake.
> > > > > But,
> > > > > > this sounds pretty reasonable, given that for squares it's
> n^2/12.
> > > This
> > > > > > means that it performs worse, asymptotically, than a square of
> > > points.
> > > > > >
> > > > > > In case anyone wants to check the work, I got that for a square
> > with
> > > > > > sidelength r0 in a circle of radius r, there is a region of area
> > > > > >   A  -(1/2) r0 (-r0/2 + sqrt(r^2 - r0^2/4)) + r^2 (pi/2 - 2
> > > > > arcsin(r0/2r))
> > > > > > where the center of the square can be. Then the full number of
> > > > > > possibilities is integral( A * (pi/2)r0,  for r0 from 0 to r).
> > > > > >
> > > > > > It seems natural to think about symmetric convex shapes
> (squircles
> > > and
> > > > > > friends?) in the plane, and then optimize over the shape to find
> > the
> > > > one
> > > > > > that produces the largest number of squares inside. In theory,
> > > probably
> > > > > > possible to derive a diff eq for the ideal shape of the curve. In
> > my
> > > > > > opinion, that would have a very high chance of being
> asymptotically
> > > > > optimal
> > > > > > for the sequence. (Although probably quite hard to prove!)
> > > > > >
> > > > > > -- Alexander Meiburg
> > > > > >
> > > > > >
> > > > > > On Fri, Oct 1, 2021 at 1:42 PM Benoît Jubin <
> > benoit.jubin at gmail.com>
> > > > > wrote:
> > > > > >
> > > > > > > > Benoit,  Thanks for the lovely example for n=49 !
> > > > > > >
> > > > > > > That shows that a(49)>=202 if I counted correctly, but Sascha
> has
> > > an
> > > > > > > example with 205 apparently.
> > > > > > >
> > > > > > > Peter, Sascha: can you give me your optimal configurations ?
> > (best
> > > > > > > would be: in place of an "x" to denote a vertex, put the number
> > of
> > > > > > > squares it belongs to)
> > > > > > >
> > > > > > > Neil: since Sascha is on a 3-day trip, I may wait Monday or
> > Tuesday
> > > > to
> > > > > > > update the entry, if that's ok with you.
> > > > > > >
> > > > > > > Benoît
> > > > > > >
> > > > > > >
> > > > > > > > Best regards
> > > > > > > > Neil
> > > > > > > >
> > > > > > > > Neil J. A. Sloane, Chairman, OEIS Foundation.
> > > > > > > > 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> > > > > > > > Also Visiting Scientist, Math. Dept., Rutgers University,
> > > > > Piscataway, NJ.
> > > > > > > > Phone: 732 828 6098; home page: http://NeilSloane.com
> > > > > > > > Email: njasloane at gmail.com
> > > > > > > >
> > > > > > > >
> > > > > > > >
> > > > > > > > On Fri, Oct 1, 2021 at 1:54 PM Benoît Jubin <
> > > > benoit.jubin at gmail.com>
> > > > > > > wrote:
> > > > > > > >
> > > > > > > > > > I saw that Peter, Sascha, ... observed that moving corner
> > > > points
> > > > > to
> > > > > > > just
> > > > > > > > > > outside the middle of the edges did better than the
> square
> > > > array.
> > > > > > > When
> > > > > > > > > > does this beat the square array?  And does it produce a
> > case
> > > > when
> > > > > > > b(n) >
> > > > > > > > > > a(n)?  That now seems very likely!
> > > > > > > > >
> > > > > > > > >
> > > > > > > > > For the moment, all points are on the grid, so there is no
> > > > witness
> > > > > > > > > that a(n) and b(n) may differ.  What they mean, I think, is
> > for
> > > > > > > > > instance for m = 7:
> > > > > > > > > ....x....
> > > > > > > > > ..xxxxx..
> > > > > > > > > .xxxxxxx.
> > > > > > > > > .xxxxxxx.
> > > > > > > > > xxxxxxxxx
> > > > > > > > > .xxxxxxx.
> > > > > > > > > .xxxxxxx.
> > > > > > > > > ..xxxxx..
> > > > > > > > > ....x....
> > > > > > > > > This wins over the square, because a corner was in 6
> squares
> > > (so
> > > > we
> > > > > > > > > lose 4*6 - 1 squares), whereas the added midpoints are in 7
> > > > squares
> > > > > > > > > each, plus 1 common square through the four midpoints. So
> it
> > > > > should be
> > > > > > > > > a +6 win.
> > > > > > > > >
> > > > > > > > > Benoît
> > > > > > > > >
> > > > > > > > > --
> > > > > > > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > > > > > > >
> > > > > > > >
> > > > > > > > --
> > > > > > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > > > > >
> > > > > > > --
> > > > > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > > > > >
> > > > > >
> > > > > > --
> > > > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > > >
> > > > > --
> > > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > > >
> > > >
> > > > --
> > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > >
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>

More information about the SeqFan mailing list