The total complexity of the cells in a line arrangement that are cut by another line is at most 15n/2. The complexity of cells cut by a convex k-gon is O(n α(n,k)). The first bound is tight, but it remains open whether the second is, or whether only linear complexity is possible.
This is the report from the ACM Workshop on Computational Topology run by Marshall and myself in Miami Beach, June 1999. It details goals, current research, and recommendations in this emerging area of collaboration between computer science and mathematics.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.