A closed topological disk $K$ is approximated by the maximal subset of faces of the square tiling that are contained in the interior of $K$. As $K$ is translated and/or rotated in the plane, the approximation changes. How many different approximations (up to translations) can be obtained in this way? What is an algorithm to explicitly construct every approximation, or at least most such approximations?

(The picture below is from Wikipedia; here, $K$ is the blue curve plus its interior, and the approximation is the green polygon plus its interior.)



Below 'face' means 'face of the unit square tiling'.

Let $K$ be a two-dimensional set which is a closed topological disk. A congruent copy of $K$, denoted $K^\ast$, is placed on the unit square tiling in some position and orientation. The faces are partitioned into three disjoint subsets:

  • those in the interior of $K^\ast$ (finitely many),
  • those dissected by the boundary of $K^\ast$ (finitely many),
  • those in the exterior of $K^\ast$ (infinitely many).

Let $A_i$ (the inner approximation) denote the set of faces that lie completely in the interior of $K^\ast$.

Let $A_o$ (the outer approximation) denote the set of faces that have non-empty intersection with $K^\ast$.

In general, both $A_i$ and $A_o$ depend on the position and the orientation of $K^\ast$. As $K^\ast$ is translated and/or rotated in the plane, distinct approximations are produced.

If that helps, $K$ may be restricted to be convex and/or have polygonal boundary; but in general $K$ may be any closed topological disk whose boundary has an efficient representation. Intuitively, 'efficient' means the following:

  1. A small finite number of real parameters suffices to describe an arbitrary shape $K$ (e.g. in the polygonal case it suffices to give coordinates of vertices; if $K$ is an ellipse, it suffices to give coefficients of an implicit equation, etc.)
  2. Translations and rotations of $K$, testing membership in the interior of $K$, etc. are not too hard to compute, in comparison to the special case when $K$ is a convex polygon.


I suspect at least some of the questions below are hard problems. Any relevant references/suggestions are appreciated.

From the practical viewpoint, I'm specifically interested in 'generate/enumerate' and 'estimate' problems for inner approximations. Other questions are probably more theoretical.

The next questions consider inner approximations equivalent if they are translations of each other.

  • (Exact) Let $S_i$ be the set of all possible inner approximations (when $K^\ast$ is placed on the unit square tiling in all possible ways).
    • How many distinct approximations are in $S_i$, up to translations? (This is finite. Every inner approximation is contained in the bounding circle of $K^\ast$, whose area is finite; hence there are only finitely many faces of the tiling inside $K$, therefore finitely many ways to choose a subset of them.)
    • What is 'average' area of an inner approximation?
  • (Asymptotic) What can be said about the number of distinct inner approximations as $K$ is scaled up (increasing its size but preserving the shape)?
  • (Estimate) What are upper and/or lower bounds on the number of inner approximations?
  • (Generate/enumerate) How to construct explicitly every inner approximation for a given shape $K$?

The next questions do distinguish approximations that are translations of each other.

  • (Count with translations in a finite region) Suppose there is a two-dimensional region $R$ taken from the same class as $K$. The region $R$ is fixed on the unit square tiling in some position and orientation. For every way to place $K^\ast$ inside $R$, one can find the inner approximation as before.
    • How many distinct inner approximations are obtained this way?
    • What are upper/lower bounds on the count?

Analogous questions can be stated for outer approximations as well. (Should one expect the answers to be essentially the same for inner vs. outer case?).

For the 'generate/enumerate' question, it is not even clear to me how to find any algorithm. One cannot 'iterate over all possible positions and orientations' because these change continuously, and an arbitrarily small movement of $K^\ast$ can lead to a different approximation. Since this problem may be too hard to solve as it is, I would accept an algorithm that skips some approximations, as long as:

  1. all produced sets are guaranteed to be inner approximations (i.e. no faces with points outside $K^\ast$);
  2. some nontrivial guarantees exist, for example:
    • an upper bound on the percentage of skipped approximations;
    • a lower bound on the average area of a produced approximation.

Intuitively, an algorithm is considered good if it skips poor approximations more often than good ones, and if it skips as few approximations as possible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.