No subquadratic algorithm is known. An lower bound is not difficult to prove. A related question is how fast can one find a maximal set of nonintersecting arcs. This problem arises in developing an efficient, robust algorithm for computing the intersection points of segments. J.-D. Boissonnat and J Snoeyink, Efficient algorithms for line and curve segment intersection using restricted predicates , in preparation.
P is a polygon obtained by cutting a tree on the surface that spans the vertices.
However, we retain the gluing pattern by recording which pairs of polygon edges were generated by a surface cut. Give an algorithm that constructs the convex polytope from the polygon. If diameter of S is at most , then there is always such a unit circle. 7th Quadrennial Intl. Theory and Appls.