0
$\begingroup$

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?

  • 0
    @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.2011-02-23

1 Answers 1

1

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$.

  • 0
    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.2011-02-23