<p>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 <a href="http://valis.cs.uiuc.edu/~sariel/papers/msc_phd/discrete-hull.html" rel="nofollow">result</a> on this. (See also <a href="http://compgeom.cs.uiuc.edu/~jeffe/pubs/gridvis.html" rel="nofollow">here</a>.)</p>

<p>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...</p>

CC BY-SA 2.5
2010-09-28T16:07:22.403Z
2010-09-28T16:07:22.403Z
Sariel Har-Peled
<p>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.</p>

<p>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.</p>

<p>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:</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-28T06:30:57.753Z
you have some pointers that I can earn more on this?
Graviton
CC BY-SA 2.5
2010-09-28T06:34:59.130Z
@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.
Per Vognsen
CC BY-SA 2.5
2010-09-28T07:15:36.100Z
*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.
Graviton
CC BY-SA 2.5
2010-09-28T07:18:59.970Z
@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.
Per Vognsen
CC BY-SA 2.5
2010-09-28T06:25:45.053Z
2010-09-28T07:15:05.110Z
2010-09-28T07:15:05.110Z
Per Vognsen
<p>This question has been asked at <a href="https://stackoverflow.com/questions/3793510/find-the-discrete-pair-of-x-y-that-satisfy-inequality-constriants">StackOverflow</a> ( a variant of this has been <a href="https://math.stackexchange.com/questions/5289/find-range-of-x-1-x-2-where-y-min-leq-yx-1-x-2-leq-y-max">asked at Math SE</a>), but so far there is no great response. So I'm going to reask here-- with a bit of twist.</p>

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

<p>$$x&gt;=0$$
$$y&gt;=0$$
$$100 \leq x^2+y^2 \leq 200$$</p>

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

<p>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.</p>

CC BY-SA 2.5
2010-09-28T13:39:20.837Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-28T13:58:16.053Z
@Joe, it is still a 2D problem. The only thing is that the constraint equations can be polynomial functions with any degree.
Graviton
CC BY-SA 2.5
2010-09-28T14:15:51.310Z
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.
Joe Fitzsimons
<cg.comp-geom>
Find the Discrete Pair of {x,y} that Satisfy Inequality Constriants
Graviton
# Find the Discrete Pair of {x,y} that Satisfy Inequality Constriants

(Asked by: username_0 on 2010-09-28)

This question has been asked at [StackOverflow](https://stackoverflow.com/questions/3793510/find-the-discrete-pair-of-x-y-that-satisfy-inequality-constriants) ( a variant of this has been [asked at Math SE](https://math.stackexchange.com/questions/5289/find-range-of-x-1-x-2-where-y-min-leq-yx-1-x-2-leq-y-max)), 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.

**Tags:** cg.comp-geom

> **Comments:**
> **username_1**: 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.  
> **username_0**: @Joe, it is still a 2D problem. The only thing is that the constraint equations can be polynomial functions with any degree.  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_3 on 2010-09-28. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: you have some pointers that I can earn more on this?  
> **username_3**: @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.  
> **username_0**: *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.  
> **username_3**: @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.  

---

### Answer by username_2 on 2010-09-28. Score: 3

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](http://valis.cs.uiuc.edu/~sariel/papers/msc_phd/discrete-hull.html) on this. (See also [here](http://compgeom.cs.uiuc.edu/~jeffe/pubs/gridvis.html).)

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...


---

