<p>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) </p>

CC BY-SA 3.0
2012-11-28T00:00:28.213Z
2012-11-28T00:00:28.213Z
Suresh Venkat
<p>I'm courrently rading "Computational Geometry" from Mark de Berg, Otfried Cheong,
Marc van Kreveld, Mark Overmars and found the following theorem 13.9.</p>

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

<p>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.</p>

CC BY-SA 3.0
2012-11-27T23:24:44.627Z
The complexity of a union of objects is the number of pieces in the boundary of the union.
Suresh Venkat
CC BY-SA 3.0
2012-11-27T23:29:22.377Z
so the number of vertexes? Is it the same for "complexity of the Minkowski sum is linear"?.
complx
CC BY-SA 3.0
2012-11-27T23:36:21.440Z
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)
Suresh Venkat
CC BY-SA 3.0
2012-11-27T23:43:53.237Z
thx this helps me quite a bit. What constraint apply for these objects? Couldn't I always describe the boundary by one single object (the object itself)?
complx
CC BY-SA 3.0
2012-11-27T23:46:07.470Z
This is possibly veering off scope. But consider the case when you have two disks that intersect. the union cannot be described by any of the two disks: it includes pieces from both of them
Suresh Venkat
CC BY-SA 3.0
2012-11-27T23:51:00.590Z
Yeah you are right. Thx for the fast responses, I think I got the Idea behind this concept. If you write your comments into an answer I would like to accept this answer.
complx
CC BY-SA 3.0
2012-11-28T04:55:24.673Z
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)$.
David Eppstein
CC BY-SA 3.0
2012-11-28T21:03:52.313Z
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. http://www.springerlink.com/content/q3917g253g836885/
Joe
<cg.comp-geom>
Complexity of union (computational geometry)
complx
# Complexity of union (computational geometry)

(Asked by: username_0 on 2012-11-27)

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.

**Tags:** cg.comp-geom
> **Comments:**
> **username_1**: The complexity of a union of objects is the number of pieces in the boundary of the union.  
> **username_0**: so the number of vertexes? Is it the same for "complexity of the Minkowski sum is linear"?.  
> **username_1**: 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)  
> **username_0**: thx this helps me quite a bit. What constraint apply for these objects? Couldn't I always describe the boundary by one single object (the object itself)?  
> **username_1**: This is possibly veering off scope. But consider the case when you have two disks that intersect. the union cannot be described by any of the two disks: it includes pieces from both of them  
> **username_0**: Yeah you are right. Thx for the fast responses, I think I got the Idea behind this concept. If you write your comments into an answer I would like to accept this answer.  
> **username_2**: 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)$.  
> **username_3**: 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. http://www.springerlink.com/content/q3917g253g836885/  

---

## 1 answers

### Answer by username_1 on 2012-11-28. Score: 6 | Accepted answer

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)


---

