Themedial axisof a polygon is the set of interior points with more than one closest point on the polygon boundary. The medial axis of an n-gon is a tree consisting of O(n) straight line segments and parabolic arcs. The parabolic arcs are equidistant from a reflex (concave) vertex and an "opposing" edge -- if the polygon is convex, then there are only straight line segments. In the general case, each vertex of the medial axis has degree three, although higher-degree vertices are possible in degenerate cases. The medial axis is a subset of the Voronoi diagram of the edges and vertices of the polygon. (Voronoi edges that meet the reflex vertices are not part of the medial axis.)The definition generalizes immediately to higher dimensions. In three dimensions, the medial

surfaceof a polyhedron consists of several quadric surface patches -- portions of planes, cones, paraboloids, parabolic cylinders, hyperbolic paraboloids -- sewn together along curve segments of algebraic degree 4. In the general case, each curve bounds three faces, and six faces and four curves meet at each vertex. If the polyhedron is convex, then the medial surface is made up entirely of planar polygonal patches, meeting in straight line segments. Again, the medial surface is a subset of the Voronoi diagram of the vertices, edges and faces of the polyhedron.

What is the worstcase complexity of the medial surface of a polyhedron?It is generally believed that the correct answer is Theta(n^{2}). However, the best known upper bound is O(n^{3+c}) for anyc>0, and even this is not easy to prove! (Any threedimensional Voronoi diagram is the projection of the lower envelope of several fourdimensional surfaces; the upper bound follows from bounds on the worstcase complexity of lower envelopes by Micha Sharir and others.)It is quite easy to construct a polyhedron whose medial surface has Omega(

n^{2}) faces. For example, we can carve out two shallow cylindrical "trenches", each withn/2 facets, from the top and bottom of a cube, in perpendicular directions. (The depth of the trenches is exaggerated in the figure.)More surprisingly, a single pair of polyhedron facets can induce Omega(

n^{2}) faces in the medial surface, as shown by the following construction, appropriately dubbed the "iron maiden pizza box" by Tim Culver. Start with a rectangular box with height 1, widthn, and depthn, resting on thexyplane and aligned with the coordinate axes. Add O(n) extremely thin horizontal spikes pointing into and almost all the way across the box, half parallel to thexaxis atz=2/5 and half parallel to theyaxis atz=3/5, with successive spikes in each family at distance 2. (If we like, we can eliminate the multiplyconnected and parallel facets by triangulating the facets and perturbing the vertices.) The top and bottom facets of the box induce a quadratic number of medial surface features, all in the planez=1/2.This construction shows a direct connection with another open problem.

What is the worstcase complexity of the Voronoi diagram of a set of lines in 3space?Again, the best known bounds are O(n^{3+c}) and Omega(n^{2}). (It has been known for decades that the Voronoi diagram of a set ofpointsin 3space has only quadratic complexity in the worst case.) For any setLof lines in 3space, we can construct a simplyconnected polyhedron whose medial surface approximates the Voronoi diagram ofLarbitrarily closely -- simply replace each line inLby a thin spike poking into an extremely large cube. So there's no hope of improving the complexity bounds for medial surfaces without first understanding the Voronoi diagram of lines.An

offset surfacefor a polyhedron is the set of points at a given distancerfrom its boundary, or equivalently, the boundary of the Minkowski sum of the polyhedron and a ball of radiusr.What is the worstcase complexity of an offset surface of a polyhedron?Whenr=0, the offset surface is the original polyhedron; as we increaser, the vertices and edges of the offset surface trace out the edges and faces of the medial axis. Although offset surfaces have lower complexity than medial surfaces, the best known upper bound on their worstcase complexity is still O(n^{3+c}). Offset surfaces can have quadratic complexity (see the examples above).Pankaj Agarwal and Micha Sharir have recently shown that the offset surface of any polyhedron with

nfeatures, or in fact of any collection ofnpoints, lines, line segments, and triangles, has at most O(n^{5/2+c}) vertices, an improvement of roughlyn^{1/2}over the previously best bound. So far at least, their proof does not extend to medial surfaces. [A preliminary version of their results, with a weaker O(n^{8/3+c}) bound, and only for lines and line segments, will appear at SODA 99.]Better answers are known for some of these questions in nonEuclidean metrics. Boris Aronov and Micha Sharir showed that in any polyhedral metric, offset surfaces of polyhedra have complexity between Omega(

n^{2}alpha(n)) and O(n^{2}logn). Paul Chew, Klara Kedem, Micha Sharir (again!), Boaz Tagansky, and Emo Welzl showed that the Voronoi diagram of lines in a polyhedral metric has complexity O(n^{2}lognalpha(n)). (Here, alpha(n) is the inverse Ackermann function.) I don't know if these results have been extended to medial surfaces.The complexity of straight skeletons in three dimensions and the mitered offset surfaces that define them is also open. Once again, the best known lower bounds are quadratic, while the best known upper bounds are cubic.

Of course, we can go to four or even higher dimensions and ask the same questions. Boris Aronov has a construction of

nlines inddimensional space whose Euclidean Voronoi diagram has complexity Omega(n^{d-1}). The best known upper bound is O(n^{d+c}).