Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am given a 2D convex polygon ( given in terms of coordinate of the vertices), and I want to lay it on a grid with an undetermined uniform square grid size, $x$.

Now, my task is to choose $x$ such that, regardless of the size and the shape of the polygon, the number of the grid, $G_n$, inside, or intersecting the polygon must remain roughly the same. $G_n$ is a constant that is given.

Some additional info: $x$ should be relatively small compare to the dimension of the polygon, and so, $G_n$ should be quite big ( $>100$)

What is the algorithm to do this? Note that the polygon can be of any size and shape, as long as it is convex.

I understand that the definition is a bit loose here, but I wonder whether anyone has done any research on this, to help to clarify all the concepts?

share|cite|improve this question
You could choose $x$ enormous, then $G_n$ is either 0 or 1-that's not much variation. Or you could choose $x$ very small, then $G_n$ is well approximated by area/x^2. The variation will be small in relative terms. What is your criterion? And what information do you have about the polygon before choosing $x$? – Ross Millikan Feb 23 '11 at 3:17
I don't think convex matters, as lattice points moving in and out as you change the spacing is local. You probably want to avoid spacings that put points parallel to one of the sides, as a small change can move lots of points in or out. But without more description of how the polygon is presented and what you mean by "roughly the same", I don't think we can do much. Vote to close. – Ross Millikan Feb 23 '11 at 3:57
@Ross, what do you mean by how the polygon is presented? – Graviton Feb 23 '11 at 4:07
You are given some information that defines the polygon. What is it? For example, side lengths and angles, or coordinates of the vertices? I'm not sure it matters-probably the figure of merit of roughly the same is more important. Generally, smaller $x$ will be better because the number that move in and out will be proportional to the perimeter (linear in $x$), while the number inside will be proportional to the area (quadratic in $x$). So what is the cost of decreasing $x$? The naive thing is to make it as small as possible. – Ross Millikan Feb 23 '11 at 4:20
@Ross, that $x$ is dependent on $G_n$, which is a constant specified by the problem statement. The polygon is given in terms of coordinates of the vertices. – Graviton Feb 23 '11 at 5:52

I think I'm a little confused what you mean by 'must remain the same' - must remain the same under what transformations (or other operations)? In general (assuming that you want $G_n$ to be invariant under translational displacement with respect to the grid), this is impossible; choose as the given polygon a (convex) quadrilateral in general position with all vertex positions (relative to the 'top' vertex) and all line slopes transcendental. Then whatever the grid size, if the top vertex is positioned precisely on some reference grid point, none of the edges of the polygon and none of the other vertices can pass through a grid point. This means that the polygon can be shifted vertically some small amount to bring the reference grid point either inside or outside without changing the status of any other grid points, thus changing your value of $G_n$.

share|cite|improve this answer
sorry! I didn't make it clear. I don't require $G_n$ to remain absolutely the same for any polygon, just that it must more or less the same, question updated. – Graviton Feb 23 '11 at 2:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.