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

Neil Sloane njasloane at gmail.com
Sat Oct 2 07:27:51 CEST 2021


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



More information about the SeqFan mailing list