1
$\begingroup$

I'm courrently rading "Computational Geometry" from Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars and found the following theorem 13.9.

Let $S$ be a collection of convex polygonal pseudodiscs with n edges in total. Then the complexity of their union is at most $2n$.

I'm not really sure what this should mean (this might be a a language barrier). First I thought that this would be the time complexity, but I'm now pretty much unsure about this.

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ The complexity of a union of objects is the number of pieces in the boundary of the union. $\endgroup$
    – Suresh Venkat
    Nov 27, 2012 at 23:24
  • $\begingroup$ so the number of vertexes? Is it the same for "complexity of the Minkowski sum is linear"?. $\endgroup$
    – complx
    Nov 27, 2012 at 23:29
  • $\begingroup$ In the plane "complexity of boundary" is equivalent (upto a constant factor) to "number of vertices" (and yes this is the same "complexity" as that for Minkowski sum). But in general the boundary complexity is the sum of complexities of all objects needed to describe the boundary (vertices, edges, faces, and so on). It's just that in the plane the number of vertices in the boundary is the same as the number of edges (because the boundary is a set of cycles in this case) $\endgroup$
    – Suresh Venkat
    Nov 27, 2012 at 23:36
  • 3
    $\begingroup$ Maybe it would be helpful to contrast with an example where the complexity is nonlinear. So imagine that you have a collection of long thin axis-parallel rectangles, half of them long in the horizontal direction and half of them long in the vertical, so that each horizontal one crosses each vertical. Then the union is a nonconvex shape with a lot of holes in it. If you describe the exterior and each hole as a sequence of points connected by line segments, the complexity is $\Theta(n^2)$. $\endgroup$
    – David Eppstein
    Nov 28, 2012 at 4:55
  • 2
    $\begingroup$ There's a whole line of research as to what types of objects have good union complexity. Basically, if the objects are "fat", disjoint, or have low density, then you don't end up with the kind of quadratic complexity David illustrated (at least in the plane). See e.g. springerlink.com/content/q3917g253g836885 $\endgroup$
    – Joe
    Nov 28, 2012 at 21:03

1 Answer 1

Reset to default
6
$\begingroup$

The complexity of a union of objects is the number of pieces in the boundary of the union. In the plane "complexity of boundary" is equivalent (upto a constant factor) to "number of vertices". But in general the boundary complexity is the sum of complexities of all objects needed to describe the boundary (vertices, edges, faces, and so on). It's just that in the plane the number of vertices in the boundary is the same as the number of edges (because the boundary is a set of cycles in this case)

Improve this answer
$\endgroup$

Your Answer

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

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