>Given a matrix describing a set of lines, I want to find the vertices of the

>polyhedron defined by that matrix. More to the point, I want to find all

>the intersections of the lines (they do not necessarly form a polyhedron).

This is the convex hull problem in disguise.

I'm going to assume two things. (1) The polygon you want is the one

containing the origin. [A set of n lines defines about n^2/2 different

polygons.] (2) None of the lines actually passes thorough the origin.

[Otherwise, just move all the lines by the same (small) amount.] In

other words, in addition to specifying the lines, you also have to

specify one point in the interior of the polygon you want, and I'm

assuming that this point is the origin (0,0).

For each line ax+by=c, write down its "dual" point (a/c, b/c).

Construct the convex hull of these dual points AND THE ORIGIN. (This is

a technical point to deal with the case where the ansewr is unbounded.

If the polygon you want is bounded, the origin will be in the interior

of the convex hull.) Each edge of this dual convex hull is bounded by a

line of the form ex+fy=g, and its dual point (e/g, f/g) is a vertex of

the polygon you want.

Now all you need is a convex hull algorithm. See the FAQ, or Joe

O'Rourke's textbook "Computational Geometry in C". Joe's textbook also

talks about point-line duality.

--

Jeff Erickson Center for Geometric Computing

http://www.cs.duke.edu/~jeffe