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
    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$?2011-02-23
  • 0
    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.2011-02-23
  • 0
    @Ross, what do you mean by `how the polygon is presented`?2011-02-23
  • 0
    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.2011-02-23
  • 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