Dynamic Connectivity in Disk Graphs.

Let be a set of in the plane, so that every site has an . Let be the defined by , i.e.

Maximum Matchings in Geometric Intersection Graphs.

Let be an intersection graph of geometric objects in the plane. We show that a maximum matching in can be found in time with high probability, where is the density of the geometric objects and is a constant such that matrices can be multiplied in time. The same result holds for any subgraph of , as long as a geometric representation is at hand.

No-Dimensional Tverberg Theorems and Algorithms.

Tverberg's theorem states that for any and any set of at least points in dimensions, we can partition into subsets whose convex hulls have a non-empty intersection. The associated search problem of finding the partition lies in the complexity class , but no hardness results are known. In the Tverberg theorem, the points in have colors, and under certain conditions,  can be partitioned into sets, in which each color appears exactly once and whose convex hulls intersect.