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.

  • 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