4
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ I don't know of any way to compute the area without computing the polygon. The simplest algorithm is just to repeatedly clip the polygon with successive halfplanes. There are highly optimized clipping algorithms. $\endgroup$ Jan 24, 2012 at 16:00
  • $\begingroup$ So just to understand you correctly: You are not interested in an areaOfPoygonAlgorithm where the vertices of the polygon are already known, right? $\endgroup$
    – Martin
    Dec 13, 2015 at 10:31

2 Answers 2

2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Great suggestions -- thanks. In my case I have a collection of points within an r-ball of a distinguished point p and want to know the area of p's Voronoi cell. Therefore, a good heuristic may be to maintain a bounding box (as you suggest) and arrange the cuts according to the distance of each neighbor from p. $\endgroup$ Jan 24, 2012 at 18:58
  • $\begingroup$ @TerronaBell I have the same situation. What did you end up using? $\endgroup$ Mar 16, 2018 at 20:47
0
$\begingroup$

This more of a musing (and perhaps amusing) than an answer. I find it worthy of cogitation.

If you have a bounding box (sheet of paper), you could try dividing it by hyperplanes (cutting off pieces with a straight blade) and measuring the area of the pieces cut off. One interesting aspect is to arrange the cuts so that the pieces obtained have very few sides, making the computation of the discards easier. Looking for an optimal such order of cutting is likely NP-hard, but even a suboptimal order may help with the computation, especially if the hyperplanes are fed to the algorithm one at a time.

If you do find this worthy, some credit should go to Robert (sp?) Fulghum.

Gerhard "Yes, I Do Kindergarten Math" Paseman, 2012.01.24

$\endgroup$
1
  • 1
    $\begingroup$ I just noticed that I repeated the essence of Joseph O'Rourke's comment to the question. I will wiki this so that he can elaborate on his comment using this answer. Gerhard "Sometimes I Do Pay Attention" Paseman, 2012.01.24 $\endgroup$ Jan 24, 2012 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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