3

Is there a proof or disproof that the quadrilateral resulting from snapping each corner of an arbitrary rectangle to the nearest point on a regular square grid is never concave?

Arbitrary, note e.g. any orientation.

Chris Jordan
  • 139

1 Answers1

3

The key is to note that a concave vertex cannot be an extreme vertex, i.e. a concave vertex cannot be the lowest vertex, or the right most vertex, etc.

If the rectangle has sides parallel to the coordinate axes, then it remains a rectangle after snap.

If the rectangle has no sides parallel to the coordinate axis then each vertex is an extreme vertex. It's easy to see that each extreme vertex remains an extreme vertex after a snap. Therefore each convex vertex remains a convex vertex (or at worst a straight vertex).

It follows that the snapped quadrilateral is never concave (although it may be degenerate).

EuYu
  • 41,421
  • "It's easy to see that each extreme vertex remains an extreme vertex after a snap." That's the bit I don't see :) – Chris Jordan Oct 17 '18 at 11:33
  • I don't see it as obvious either. For it to become concave, a vertex has to cross over the diagonal between the two adjacent vertices. Taking the grid size as a unit, a vertex moves at most $\sqrt{2}/2$, and the diagonal can move at most that same distance, so if the original rectangle's vertices are more than $\sqrt{2}$ from its diagonal, it won't become concave. We need a narrow rectangle, but then the vertices tend to snap to the same grid point, becoming a degenerate quadrilateral instead of concave. I can't quite prove it won't happen though. – Jaap Scherphuis Oct 17 '18 at 13:34
  • @ChrisJordan Snapping is just an application of the nearest integer function to the coordinates of the rectangle. The fact that extreme vertices remain extreme is a consequence of the fact that the nearest integer function is an order-preserving function, $x\le y \implies f(x)\le f(y)$. The same argument would apply to any order preserving function actually. – EuYu Oct 17 '18 at 18:54
  • 1
    It was not obvious to me at first glance, but if we consider the "bounding box" of each quadrilateral--the smallest rectangle with sides parallel to the axes that contains the given quadrilateral--it seems clear enough that a point on an edge of the bounding box before snapping will be on an edge of the bounding box after snapping, and this guarantees it is not a concave vertex. – David K Oct 18 '18 at 00:15
  • @EuYu Because the function is applied independently to x and y, the fact it is order-preserving isn't enough to satisfy me that an extreme vertex remains extreme. – Chris Jordan Oct 18 '18 at 00:44
  • @DavidK Vertices on the your bounding box are precisely what I called extreme vertices, i.e., the topmost, or rightmost, etc, vertices. – EuYu Oct 18 '18 at 03:30
  • @ChrisJordan Take the rightmost vertex for example. It is, by definition, the vertex with the largest $x$ coordinate. Since the nearest integer function is order preserving, it will remain the vertex with the largest $x$ coordinate (possibly degenerate). Therefore it remains an extreme vertex. – EuYu Oct 18 '18 at 03:32
  • Yes, exactly, the bounding box is a way to keep track of the extreme vertices. That is how I concluded that this answer is correct. – David K Oct 18 '18 at 04:42
  • The main insight (which I missed) that proves the result is that snapping to the nearest grid point (by Euclidean distance) is equivalent to rounding each coordinate separately to the nearest integer. Once you have that, it does indeed become fairly obvious. – Jaap Scherphuis Oct 18 '18 at 08:52
  • OK, I'm convinced. Thanks all! – Chris Jordan Oct 18 '18 at 21:47