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.

$\endgroup$
  • 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 '12 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 '12 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 '12 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 '12 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 '12 at 21:03
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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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