User - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T07:16:03Z http://mathoverflow.net/feeds/user/27203 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110604/properties-of-the-minimum-circumscribing-circle-for-points-sequentially-placed-wi Properties of the minimum circumscribing circle for points sequentially placed within a circle of radius $r$ of previously placed points on a 2D plane unknown (yahoo) 2012-10-25T01:09:19Z 2012-10-27T00:30:08Z <p>Imagine I perform the following procedure:</p> <p>[1] At time point $t_1$, I place a single point on a two-dimensional plane at the coordinate $(x, y) = (0, 0)$. </p> <p>[2] At time point $t_2$, I center a circle of radius $r$ at the point placed during time $t_1$, and place another point somewhere within (or along the contour of) this circle with uniform probability across its area. </p> <p>[3] For time point $t_i$, I first randomly select a previously placed point, with uniform probability for all points, and then I center a circle of radius $r$ at the point and place another point somewhere within (or along the contour of) this circle with uniform probability across its area. </p> <p>GOTO [3] for $(N - 2)$ iterations.</p> <hr> <p>Call $(p_1, ..., p_N) \in P$ the set of points $N$ placed on the surface via the above method.</p> <p>My question is the following: What is the probability distribution for the radius and center position of the minimum circle that circumscribes (or covers) the set of $N$ points in $P$? How does this relate to the barycenter of the coordinates for the points in $P$ and the initial point at the origin?</p> http://mathoverflow.net/questions/110238/maximizing-the-number-of-lattice-points-in-a-circle-of-radius-r-placed-on-a-lat Maximizing the number of lattice points in a circle of radius $r$ placed on a lattice unknown (yahoo) 2012-10-21T15:07:10Z 2012-10-21T16:58:06Z <p>I have a circle of radius $r$, and I wish to place this circle of a $Z^2$ integer lattice or an $A_2$ hexagonal lattice s.t. I maximize the number of lattice points within or along the contour of the circle. </p> <p>Trivially, for $r &lt; \frac{R}{2}$, where $R$ is the smallest spacing between lattice points, it will be optimal to center the circle on a lattice point. However, is there an optimal position within the fundamental unit of either lattice if $r \geq T$, where $T$ is some threshold value?</p> <p>Taking a guess for the $Z^2$ integer lattice, I'd say that centering the circle on a lattice point will be optimal for $r \geq \sqrt(2)$ and $r &lt; \frac{1}{2}$. For $\frac{\sqrt(2)}{2} \leq r &lt; \sqrt(2)$, the optimal position for the circle will be in the center of the square unit cell of the lattice (allowing coverage of four lattice points), and for $\frac{1}{2} \leq r &lt; \frac{\sqrt(2)}{2}$, the optimal position will between two lattice points separated by the smallest possible inter-point distance (i.e. the unit distance) s.t. the circle covers these two points. However, I don't know how to prove this. </p> <p>For an $A_2$ hexagonal lattice, we know for $r &lt; \frac{1}{2}$ that centering the circle on a lattice point will be optimal (allowing coverage of a single lattice point), and can guess that the next optimal position will be between two lattice points separated by the smallest possible inter-point distance (i.e. the unit distance) for $\frac{1}{2} \leq r &lt; \frac{1}{\sqrt{3}}$ (covering two lattice points), then at the barycenter of an equilateral triangle cell in the lattice for $\frac{1}{\sqrt{3}} \leq r &lt; \frac{\sqrt{3}}{2}$ (covering three lattice points), then, it seems, back between two lattice points separated by the unit distance for $\frac{\sqrt{3}}{2} \leq r &lt; 1$ (covering four lattice points), then back to the center of the lattice for $r = 1$ (covering seven lattice points)? Is it optimal to remain centered on a lattice point for $r > 1$?</p> <hr> <p>In a previous question ( <a href="http://mathoverflow.net/questions/110186/an-exact-counting-solution-for-the-number-of-points-within-a-circle-of-radius-r" rel="nofollow">http://mathoverflow.net/questions/110186/an-exact-counting-solution-for-the-number-of-points-within-a-circle-of-radius-r</a> ) I noted the exact counting solution for the number of points contained or along the contour of a circle of radius $r$ centered on a lattice point in a $Z^2$ integer lattice, and Yoav Kallus provided an exact counting solution for the $A_2$ hexagonal lattice. </p> <p>We can note that, if $D$ is the largest spacing between lattice points in an arbitrary lattice ($D = \sqrt(2)$ on a $Z^2$ integer lattice and $D = 1$ on an $A_2$ hexagonal lattice), then a circle of radius $(r + D)$ centered on a lattice point will always cover more lattice points than a circle of radius $r$ centered at arbitrary coordinates. </p> http://mathoverflow.net/questions/110186/an-exact-counting-solution-for-the-number-of-points-within-a-circle-of-radius-r An exact counting solution for the number of points within a circle of radius $r$ centered on a lattice point in a $A_2$ hexagonal lattice unknown (yahoo) 2012-10-20T20:25:17Z 2012-10-20T22:31:15Z <p>In a previous question: (http://mathoverflow.net/questions/109515/the-gauss-circle-problem-on-a-hexagonal-lattice) I asked for an analytic approximation for the number of lattice points in or along the contour of a circle centered on a lattice point in an $A_2$ hexagonal lattice. The user emiliocba noted that such an approximation was provided by: </p> <p>Lax, P.D., Phillips, R.S. The asymptotic distribution of lattice points in Euclidean and non-Euclidean spaces. J. Funct. Anal. 46(3), pp. 280 – 350 (1982). </p> <p>With a best current error term of $O(r^{\frac{2}{3}})$ provided by:</p> <p>Levitan, B.M. Asymptotic formulae for the number of lattice points in Euclidean and Lobachevskii spaces. Russian Mathematical Surveys 42(3), pp. 13 - 42 (1987).</p> <hr> <p>My question is now if there exists an exact counting solution for the number of points within a circle of radius $r$ centered on a lattice point in an $A_2$ hexagonal lattice. We know that an exact counting solution exists for the $Z^2$ integer lattice using the Floor[] function (see - <a href="http://mathworld.wolfram.com/GausssCircleProblem.html" rel="nofollow">http://mathworld.wolfram.com/GausssCircleProblem.html</a> ): </p> <p>$N(r) = 1 + 4*Floor[r] + 4*\sum^{Floor[r]}_{i=1} Floor[(r^2-i^2)^{\frac{1}{2}}]$</p> <p>Can we write a similar counting function for the $A_2$ lattice?</p> <hr> <p>For a list of example values, the number of lattice points in a circle of diameter $r$ (i.e. radius $\frac{r}{2}$) centered on a lattice point in an $A_2$ hexagonal lattice, is given in (http://oeis.org/A053416/list). </p> <p>For $n = {0, 1, 2, ...}$ we have $N(r) = {1, 1, 7, 7, 19, 19, 37, 43, 61, 73, 91}$.</p> http://mathoverflow.net/questions/109515/the-gauss-circle-problem-on-a-hexagonal-lattice The Gauss circle problem on a hexagonal lattice unknown (yahoo) 2012-10-13T04:38:37Z 2012-10-20T11:37:02Z <p>Take an infinite hexagonal lattice (or equivalently, an equilateral triangular lattice), with unit spacing between the closest lattice point pairs, and draw a disc of radius $r$ centered on a lattice point at $(0, 0)$. Let $N(r, hex)$ denote the number of hexagonal lattice points at coordinates $(a, b)$ s.t. $(a^2 + b^2) \leq r^2$, i.e. the number of lattice points on or within the aforementioned disc of radius $r$. </p> <p>Are there any literature references for approximations to $N(r, hex)$ (I haven't been able to find any through a Google search)? What is an exact counting solution for $N(r, hex)$? </p> <p>Using the exact counting solution for the $Z^2$ integer lattice, (http://mathworld.wolfram.com/GausssCircleProblem.html) I suppose we can guess a lowerbound for the hexagonal lattice of:</p> <p>Lowerbound $N(r, hex) = 1 + Floor[\frac{r}{2}] + 4*\sum^{Floor[\frac{r}{2}]}_{i=1} Floor[((\frac{r}{2})^2-i^2)^{\frac{1}{2}}] + 2*Floor[r]$</p> <p>Where we simply overlay the $Z^2$ lattice with (closest) nearest-neighbor spacing $2$ on top of an $A_2$ hexagonal lattice with (closest) nearest-neighbor spacing $1$, and add an additional $2*Floor[r]$ correctional term.</p> <p>[10/13/12] The OEIS sequences are extremely helpful, but after searching the literature for awhile, I'm still having difficulty finding an exact (counting) solution for the number of lattice points within a circle of real number radius $r$. Any references would be very much appreciated! </p> <p>[10/14/12] Still no luck finding a reference in the literature. Surely someone has looked at this problem for, say, graphene and other molecular or atomic lattices where one would like to have a precise atom count a certain physical distance away from one atom?</p> <hr> <p>[10/19/12] I managed to find the exact OEIS sequence I was looking for: <a href="http://oeis.org/A053416" rel="nofollow">http://oeis.org/A053416</a></p> <p>However, I'd still like to find an exact counting solution, like the one presented above the $Z^2$ integer lattice.</p> http://mathoverflow.net/questions/102749/sunrise-problem Comment by 2012-10-22T13:33:14Z 2012-10-22T13:33:14Z Wait... can I know the answer? http://mathoverflow.net/questions/110238/maximizing-the-number-of-lattice-points-in-a-circle-of-radius-r-placed-on-a-lat/110248#110248 Comment by 2012-10-21T18:05:03Z 2012-10-21T18:05:03Z Ahem, peaks in terms of the number of lattice points internal to the circle. http://mathoverflow.net/questions/110238/maximizing-the-number-of-lattice-points-in-a-circle-of-radius-r-placed-on-a-lat/110248#110248 Comment by 2012-10-21T18:04:33Z 2012-10-21T18:04:33Z @Michael Biro If a circle of radius $r$ were to execute something like a Brownian motion on a lattice, would we really only expect peaks when its center drifts over a small set of points in the fundamental unit of the Z^2 or A^2 lattices? http://mathoverflow.net/questions/110238/maximizing-the-number-of-lattice-points-in-a-circle-of-radius-r-placed-on-a-lat/110248#110248 Comment by 2012-10-21T17:37:46Z 2012-10-21T17:37:46Z @Michael Biro &quot;I want to say that by symmetry, the only relevant centers are lattice points, midpoints of square edges, and centers of squares...&quot; right, I think that makes a lot of sense... but is there any way to make this statement rigorous? http://mathoverflow.net/questions/110186/an-exact-counting-solution-for-the-number-of-points-within-a-circle-of-radius-r/110201#110201 Comment by 2012-10-20T22:19:59Z 2012-10-20T22:19:59Z @Yoav I was following what Will Sawin was doing, but to make sure I understand, could you quickly note your approach? http://mathoverflow.net/questions/110186/an-exact-counting-solution-for-the-number-of-points-within-a-circle-of-radius-r/110190#110190 Comment by 2012-10-20T21:48:07Z 2012-10-20T21:48:07Z @Will Sawin Hmm... I don't see the error. http://mathoverflow.net/questions/110186/an-exact-counting-solution-for-the-number-of-points-within-a-circle-of-radius-r/110190#110190 Comment by 2012-10-20T21:35:13Z 2012-10-20T21:35:13Z With: Table[1 + 2*Floor[r] + 2*Floor[r/3^(1/2)] + 4*Sum[Floor[((4*r^2 - 4*i^2)/3)^(1/2)], {i, 1, Floor[r]}] + 4*Sum[Floor[((4*r^2 - (2*i + 1)^2)/3)^(1/2) + 1/2], {i, 0, Floor[r - 1/2]}], {r, 0, 10}] ... I'm getting the table: {1, 7, 31, 61, 117, 179, 259, 351, 457, 573, 723}, which doesn't match anything in OEIS... http://mathoverflow.net/questions/109515/the-gauss-circle-problem-on-a-hexagonal-lattice/110143#110143 Comment by 2012-10-20T14:14:50Z 2012-10-20T14:14:50Z @emiliocba Thanks! http://mathoverflow.net/questions/109515/the-gauss-circle-problem-on-a-hexagonal-lattice Comment by 2012-10-20T14:02:36Z 2012-10-20T14:02:36Z @Will Sawin I'm still having trouble deriving the counting solution you're hinting at... http://mathoverflow.net/questions/109515/the-gauss-circle-problem-on-a-hexagonal-lattice/110143#110143 Comment by 2012-10-20T13:42:03Z 2012-10-20T13:42:03Z @emiliocba I apologize, I did not mean an exact analytic solution, I meant a counting solution of the form presented by the sum N(r) here (for a Z^2 integer lattice): <a href="http://mathworld.wolfram.com/GausssCircleProblem.html" rel="nofollow">mathworld.wolfram.com/GausssCircleProblem.html</a> http://mathoverflow.net/questions/109515/the-gauss-circle-problem-on-a-hexagonal-lattice/110143#110143 Comment by 2012-10-20T12:13:38Z 2012-10-20T12:13:38Z @emiliocba That was my initial impression... However, what makes this harder than finding the rectangular lattice exact counting solution? Looking at Will Sawin's comment, and I hope I'm not misinterpreting here, there seems to be some notion that the same method can be extended to the hexagonal lattice in two-dimensions? http://mathoverflow.net/questions/109515/the-gauss-circle-problem-on-a-hexagonal-lattice/110143#110143 Comment by 2012-10-20T11:36:48Z 2012-10-20T11:36:48Z @emiliocba This is basically the answer that I want, but do you think an exact counting solution is possible? http://mathoverflow.net/questions/109515/the-gauss-circle-problem-on-a-hexagonal-lattice/110143#110143 Comment by 2012-10-20T11:36:04Z 2012-10-20T11:36:04Z @emiliocba Fantastic literature reference, thanks! However, looking at the paper, I think you meant to have $s \to r$. http://mathoverflow.net/questions/109515/the-gauss-circle-problem-on-a-hexagonal-lattice Comment by 2012-10-19T21:20:58Z 2012-10-19T21:20:58Z @Will Sawin If you have the time, could you elaborate a bit? I really apologize, but I'm having a bit of trouble seeing it. I don't have the reference for the derivation of the rectangular lattice counting solution. http://mathoverflow.net/questions/109515/the-gauss-circle-problem-on-a-hexagonal-lattice Comment by 2012-10-14T19:00:52Z 2012-10-14T19:00:52Z @Yemon Choi I'd be very happy with a good estimate, but an exact counting solution would be useful in any case to characterize an error term.