cp's OEIS Frontend

A293330 Minimum number of points of the square lattice falling strictly inside a square of side n that is not perfectly aligned with the square lattice.

%I A293330 #38 Jul 26 2022 22:03:29
%S A293330 0,0,2,7,12,21,32,40,57,72,96
%N A293330 Minimum number of points of the square lattice falling strictly inside a square of side n that is not perfectly aligned with the square lattice.
%C A293330 This kind of sequence is related to the practical problem of detecting regular polygons of a given size in pixellated images. This is why it explicitly excludes the minimum number of points that can be obtained with the singular case of squares that are perfectly aligned with the square lattice. Similarly for A291259 and A292060, the different regions for the centers of squares of side n (with a constant minimum number of lattice points inside them) seem to become very complex and irregular as n increases (see density plots in Links).
%C A293330 I tried several alternative algorithms to compute this sequence but they all involved some numerical procedure without exact results. These terms are estimates obtained with the proposed algorithm which for every square size: (i) makes a discrete exploration of the continuous tridimensional space that determines the container square (two coordinates for the center and one for the orientation), (ii) checks the number of points falling inside, and (iii) picks the lowest obtained number.
%C A293330 In short, these numbers have not been rigorously proved to be correct. - _N. J. A. Sloane_, Mar 31 2018
%H A293330 Andres Cicuttin, <a href="/A293330/a293330.pdf">Plots of different regions for the centers of squares of side n with constant minimum numbers of lattice points inside them</a>
%H A293330 Hugo Pfoertner, <a href="/A293330/a293330_2.pdf">Illustrations of upper bounds for the terms a(1)..a(25)</a>
%F A293330 a(n) ~ n^2.
%t A293330 (* This gives a polar function of a k-sides regular polygon with side length "side" *)
%t A293330 PolarPolygonSide[sidelength_, theta_,
%t A293330    k_] := ((sidelength/2)/Tan[Pi/k])/
%t A293330    Cos[Mod[theta - Pi/k, 2 Pi/k] - Pi/k];
%t A293330 (* {x,y}: coordinate of the test point,
%t A293330    phase: angle offset,
%t A293330    sides: number of sides *)
%t A293330 TruePointInsidePhase[x_, y_, sidelength_, phase_, sides_] :=
%t A293330   Module[{theta}, theta = ArcTan[x, y] + phase;
%t A293330    If[x^2 + y^2 == 0, 1,
%t A293330      If[x^2 + y^2 - (PolarPolygonSide[sidelength, theta, sides]^2) < 0, 1, 0]] // Return];
%t A293330 sides = 4; dstep = 0.025; phasestep = 2 Pi/300;
%t A293330 epsilon = 2Pi*10^-6; (* small initial angle to avoid a perfectly aligned square *)
%t A293330 seq = {};
%t A293330 Do[npoints = {}; k = 0;
%t A293330 Do[Do[Do[
%t A293330      Do[Do[k =
%t A293330         k + TruePointInsidePhase[i + di, j + dj, sidelength, phase, sides],
%t A293330 {i, -sidelength - 1, sidelength + 1, 1}],
%t A293330 {j, -sidelength - 1, sidelength + 1, 1}];
%t A293330      AppendTo[npoints, k];     k = 0;,
%t A293330 {dj, 0, 1/2, dstep}],
%t A293330 {di, 0, 1/2, dstep}],
%t A293330 {phase, epsilon, 2 Pi/sides, phasestep}] // Quiet;
%t A293330 temp = npoints // Min;
%t A293330 AppendTo[seq, temp]; Print[seq // Last], {sidelength, 0, 10, 1}]
%t A293330 Print[seq]
%t A293330 (*
%t A293330 (*This gives the number of points strictly inside a polygone given by
%t A293330 function "PolarPolygonSide" of "sides" sides, side length: "sidelength", centered in (-di,-dj) and rotated by "phasestep" radians wrt to initial orientation: *)
%t A293330 FaeDensityPlot[sides_, sidelength_, di_, dj_, phasestep_] :=
%t A293330 Module[{npoints = {}, kamin = {}, k = 0},
%t A293330   Quiet[Do[Do[
%t A293330      Do[k = k +
%t A293330         TruePointInsidePhase[i + di, j + dj, sidelength, phase,
%t A293330          sides], {i, -sidelength - 1, sidelength + 1,
%t A293330        1}], {j, -sidelength - 1, sidelength + 1, 1}];
%t A293330     AppendTo[npoints, k];
%t A293330     k = 0;, {phase, 0, (2 \[Pi])/sides, phasestep}]];
%t A293330   Return[Min[npoints]]]
%t A293330 (*This plots the regions for the centers of squares of side "sidelength" with constant minimum numbers of lattice points inside*)
%t A293330 sidelength=6;
%t A293330 DensityPlot[FaeDensityPlot[4, sidelength, x, y, (2 \[Pi])/300] ,{x, 0, 1/2}, {y, 0, 1/2}, PlotPoints -> 100, PlotRange -> All, ColorFunction -> "DeepSeaColors", MaxRecursion -> 3, PerformanceGoal -> "Quality", PlotTheme -> "Detailed", PlotLegends -> Automatic]
%t A293330 *)
%Y A293330 Cf. A291259, A292060.
%K A293330 nonn,hard,more
%O A293330 0,3
%A A293330 _Andres Cicuttin_, Oct 06 2017