It's true that the number of bounds is O(N), but each bound could correspond to multiple faces. For example, if you intersect two cylinders, you only have 2 bounds, but 4 (curved) faces. J.P. On Tue, Oct 21, 2014 at 1:45 PM, Warren D Smith <warren.wds@gmail.com> wrote:

QUESTION (Dan Asimov): Suppose given N bi-infinite cylinders of radius 1 in 3-space, whose axes all contain the origin. What is the maximum number of (curved) faces that their common intersection can have?

--I think the answer should be O(N) [so Grossman guess of a quadratic(N) is wrong].

Am I confused?

More generally I think, if you intersect N convex 3-dimensional objects (to get a convex result of course) and the original objects' surfaces are defined by piecewise algebraic equations with bounded degree and bounded #pieces, then the final object should enjoy O(N) bounds on its face, edge, and vertex count, and can be computed via an O(NlogN)-time "randomized incremental" algorithm. Or at least this ought to be true of objects like spheres, halfspaces, or cylinders which have the property that when you intersect two, you get 1 convex object with at most two pieces discarded (if intersection nontrivial).

The general idea to prove that is in:

K.L.Clarkson & P.W.Shor: Applications of Random Sampling in Computational Geometry, II, Discrete and Computational Geometry 4,5 (1989) 387-421.

and probably is also discussed in e.g. K.Mulmuley book.

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun