3
$\begingroup$

This question has been asked at StackOverflow ( a variant of this has been asked at Math SE), but so far there is no great response. So I'm going to reask here-- with a bit of twist.

I have a few inequalities regarding $x,y$ ( both must be integer), that satisfies the following equations:

$$x>=0$$ $$y>=0$$ $$100 \leq x^2+y^2 \leq 200$$

Is there an algorithm (non-brute force!) that allows me to find every admissible pair of $x,y$?

The $100 \leq x^2+y^2 \leq 200$ is just an example; in general the constraint equation(s) can be of polynomial functions with any degree.

$\endgroup$
3
  • $\begingroup$ I deleted my answer, as on rereading the question, it seems that you want to retain the restriction to 2D. In arbitrary dimensions the problem becomes much harder. $\endgroup$ – Joe Fitzsimons Sep 28 '10 at 13:39
  • $\begingroup$ @Joe, it is still a 2D problem. The only thing is that the constraint equations can be polynomial functions with any degree. $\endgroup$ – Graviton Sep 28 '10 at 13:58
  • $\begingroup$ Yes, I see that now. It was just the last line where I wasn't sure, but of course the title answers that. I just somehow missed it. $\endgroup$ – Joe Fitzsimons Sep 28 '10 at 14:15
7
$\begingroup$

This is a rasterization problem. For linear inequalities, the regions are polygonal. The classical approach to polygon rasterization is scan conversion; you may learn about it in any textbook on computer graphics.

Preparatory to scan conversion, you will need to convert your linear inequalities (defining half-planes) into an oriented list of edges. One way is to compute the convex hull of the dualized inequalities.

For general polynomial inequalities, the problem is considerably harder. Scan conversion with plane sweeping and active edge lists will do the trick. Detecting sweep events requires you to solve systems of polynomial equations in two variables, which may be done with a combination of numerical and symbolic methods. One way uses resultants and root finding to determine the intersection events up front. Another approach is more incremental, less efficient but significantly simpler:

Assume a bounding box is given. For each y going from the maximum to the minimum, incrementally evaluate the coefficients of the polynomials as functions of y using forward differencing, yielding polynomials depending only on x for each scan-line. Their roots will serve as the rasterization bounds for that scan-line, and you can learn how to find them in a book on numerical methods (Numerical Recipes is popular).

Edit: When I wrote my answer, the last inequality had subscripts rather than superscripts, so it appeared linear. Now I see it is quadratic. That still makes it a rasterization problem although a non-polygonal one. For this specific case you can use circle rasterization to cut out the annulus. In the most general case, you will need polynomial techniques along the lines of my last paragraph. I added some more detail on this.

$\endgroup$
4
  • $\begingroup$ you have some pointers that I can earn more on this? $\endgroup$ – Graviton Sep 28 '10 at 6:30
  • $\begingroup$ @Ngu: For the linear case, textbooks on computer graphics and computational geometry, e.g. Shirley, et al's Fundamentals of Computer Graphics and de Berg, et al's Computational Geometry. I would suggest mastering this case thoroughly before you worry about the general polynomial case. Once you get there, you will probably want to learn about resultants and root finders. $\endgroup$ – Per Vognsen Sep 28 '10 at 6:34
  • $\begingroup$ Assume a bounding box is given, one has to choose this bounding box judiciously. Choosing it too big will result in a waste of computation time, choosing it too small will result in some points being missing. This is also a hard question here. $\endgroup$ – Graviton Sep 28 '10 at 7:15
  • 2
    $\begingroup$ @Ngu: You can find the minimum and maximum y using nonlinear optimization techniques. You're right that this subproblem is a can of worms in itself. But if I keep recursing with an exposition of every subproblem you don't know about, I will end up writing a book-length treatise. $\endgroup$ – Per Vognsen Sep 28 '10 at 7:18
3
$\begingroup$

If the inequalities are linear, then each inequality corresponds to a line, and the feasible region is a convex polygon. Computing the grid points inside convex polygon is known as the discrete hull problem. See here for one result on this. (See also here.)

In general, you can compute the arrangement of the constraints, and extract the discrete points inside each relevant face. If a face is not convex, but is the difference between convex regions (as in the above example), then you can compute the discrete hull for each of the sets, compute their arrangement, triangulate each face, and compute the discrete hull for each of the regions. Notice, that it might be that a grid point hides somewhere in a very thin and very long triangle, and using discrete hull gives you a faster algorithm...

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.