9
$\begingroup$

Call a polygon with integer coordinates (in the Euclidean plane) a 'lattice polygon'. Pick's Theorem allows you to efficiently compute the number of lattice points inside this polygon given just its set of vertices.

Is there a similar method to efficiently compute the sum

$$\sum_{(x,y)\in \mathcal{P}} x$$

where $\mathcal{P}$ is some lattice polygon? In other words, are there any methods to compute the "center-of-mass" of the set of lattice points belonging to the interior/boundary of a given lattice polygon?

(By efficiently, I mean something on the order of the number of vertices of the polygon. Also, by triangulation it's clear that it suffices to answer this question for lattice triangles)

EDIT: In case it was unclear, I am not trying to find the actual center of mass of the triangle - I want to find the center of mass of the set of lattice points inside the triangle (hence the above sum).

EDIT 2: After working on this problem a bit more, I think I've arrived at a fairly simple method which seems to work and avoids the messy machinery of 3D-Ehrhart polynomials.

The idea is (just as in Pick's theorem), since we can inscribe any triangle inside a rectangle, it suffices to compute the sum for rectangles and right triangles. Computing the sum for rectangles is easy; it's just something like $(y_2-y_1)(x_1+(x_1+1)+...+x_2)$.

Because of symmetry, it's almost as simple for right triangles. Namely, the sum of x-coordinates in/on the boundary of any right triangle is just equal to ((sum of x-coordinates in the corresponding rectangle) + (sum of x-coordinates along the diagonal))/2.

Hopefully this helps anyone who later has the same problem.

  • 5
    The center of mass of a triangle is just $\frac{1}{3}$ of the sum of its three corner coordinates. So that gives a linear-time algorithm, by multiplying the cg of each triangle by its area, summing, and dividing by the total area.2011-07-31
  • 2
    @Joseph: that comment should be an answer. Incidentally, you wouldn't use Pick's theorem for the area of a triangle (method 7 of [this list of area calculations](http://www.btinternet.com/~se16/hgb/triangle.htm) if you know the vertices of the triangle, but method 6.2011-07-31
  • 1
    But it does not seem to be the center of mass of the triangle or polygon that is being sought.2011-08-01
  • 0
    @Andre, I guess the center of mass is the sum divided by the number of summands.2011-08-01
  • 2
    To be clear, I *don't* want the area of the triangle (or the actual center of mass, which is why I put it in quotes). I want to calculate the center of mass of the set of lattice points inside the triangle.2011-08-01
  • 1
    Edges of the triangle will "weigh" into the final product in proportion to the gcd of the x and y components of the associated displacement vector: I predict this could cause significant potential asymmetry and deviation from the true center of mass, and possibly give a number-theoretic flavor to the problem.2011-08-01
  • 0
    My apologies for misunderstanding the problem in my comment (and then disappearing for a day!).2011-08-01

1 Answers 1

2

It depends on what you mean by efficient. Computing $$\sum_{(x,y)\in P}x$$ is equivalent to computing the number of lattice points in a 3d polyhedron (basically $P$ with a slanted roof.) This is a job for Ehrhart polynomials. If you decompose $P$ into triangles you can decompose the triangle's corresponding polyhedron into a triangular prism (for which computing the lattice points therein is just an application of Picks Theorem) and two tetrahedra, which are straightforward to deal with, but fiddly (see the mathworld page referenced above.) All of this is explained clearly in great detail in Computing the Continuous Discretely.

  • 0
    Thanks for the Ehrhart polynomial reduction; I was aware of the theory of Ehrhart polynomials, but didn't immediately see how to reduce it to one.2011-08-01