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

Allan Wechsler acwacw at gmail.com
Sat Oct 2 16:33:43 CEST 2021 

 I think it's even worse than having to introduce pairs. I think you have
to add three off-grid points to complete a single new square. (Remember
that points with rational coordinates count as "on-grid", because a finer
grid would include them.)

On Sat, Oct 2, 2021 at 10:30 AM <rgwv at rgwv.com> wrote:

> Would not those "off the grid" points have to come in pairs?
>
> -----Original Message-----
> From: SeqFan <seqfan-bounces at list.seqfan.eu> On Behalf Of Neil Sloane
> Sent: Saturday, October 2, 2021 1:28 AM
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Subject: [seqfan] Re: How many squares can you make from n points in the
> plane?
>
> 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/
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>

More information about the SeqFan mailing list