System of Linear Inequalities in Two Variables: solving algebraically.


sergio2004
07-15-2004, 03:52 PM
Hi everybody,

I'd like to know if there is some known algorithm that allows to solve
a system of linear inequalities in two variables (x and y)
algebraically. I know how to solve it graphically
(http://home.xnet.com/~fidler/triton/math/review/mat085/linineqtwo/linineqtwo1.h
tm),
but now I need to implement an algorithm that retrieves the polygon
that contains all the pairs (x,y) that satisfy the constraints.

I would like to ask you about it before trying to reinvent the wheel
myself...

Thanks in advance,

Sergio

jaje
07-22-2004, 06:20 AM
You might want to check out the paper "Improved Algorithms for Linear Inequalities with Two Variables per Inequality" by E. Cohen and N. Megiddo. It was published in SIAM Journal of Computing, vol. 23 no. 6, pp.1313-1347. Yo can download it at http://www.research.att.com/~edith/Papers/twovar.ps .

Hope this helps.

Jan M. (^_^)