The intersection of a collection of half-planes describes a convex polygon, whose vertices can be constructed in $O(n \log n)$ time using a divide-and-conquer approach (e.g., intersect each half-plane with a bounding box and recursively merge the resulting polygons pairwise).


Suppose, however, that I'm interested only in the *area* of this polygon. Are there known algorithms for computing the area that are either 1. asymptotically faster (I'm doubtful) or 2. simpler (I'm hopeful) than those used to explicitly construct the vertices? Also of interest are algorithms that are 3. more stable in finite-precision.


Thanks!



Area of a Convex Polygon (Described via Half-Planes)
[Let me put this in a separate answer, despite
Gerhard's kind invitation :-), as I would like to de-emphasize seeking efficiencies.]


It might not be worth using a divide-and-conquer scheme, which could lead to
implementation complexities.
My inclination, as I mentioned in a comment, is to 
just incrementally clip: at any point, intersect the polygon for the first $k$ halfplanes
with the $(k+1)$-st halfplane.
Even if you have $n=10^9$ halfplanes, it is likely the
intersection will grow as $\log n$, which is the growth-rate of the convex hull of points drawn
from a uniform distribution (an old result of Dwyer).
So you would still get $O(n \log n)$ performance with a naive 
worstcase $O(n^2)$ algorithm.


If you still want efficiencies:


* Maintain a bounding box for each intermediate convex polygon for quick rejection of
superfluous clips.
* Use an efficient data structure to store the intermediate
convex polygons so that the cutting can be achieved by binary search.
* Choose carefully among the highly optimized [line-clipping algorithms](http://en.wikipedia.org/wiki/Line_clipping) developed by the
graphics community over the years.
* Finally, "arrange the cuts so that the pieces obtained have very few sides" (to quote Gerhard);
but I don't see how to do that in a way that might not cost more than the savings.


