## Abstract

We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem. (a) We review and simplify some old proofs in new disguise and give new proofs of the bound O(n√k+1) for the complexity of the k-th level in an arrangement of n lines. (b) We derive an improved version of Lovasz Lemma in any dimension, and use it to prove a new bound, O(n^{2}k^{2/3}), on the complexity of the k-th level in an arrangement of n planes in R^{3}, or on the number of k-sets in a set of n points in three dimensions. (c) We show that the complexity of any single level in an arrangement of n line segments in the plane is O(n^{3/2}), and that the complexity of any single level in an arrangement of n triangles in 3-space is O(n^{17/6}).

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Annual Symposium on Computational Geometry |

Editors | Anon |

Publisher | ACM |

Pages | 30-38 |

Number of pages | 9 |

State | Published - 1997 |

Event | Proceedings of the 1997 13th Annual Symposium on Computational Geometry - Nice, Fr Duration: Jun 4 1997 → Jun 6 1997 |

### Other

Other | Proceedings of the 1997 13th Annual Symposium on Computational Geometry |
---|---|

City | Nice, Fr |

Period | 6/4/97 → 6/6/97 |

## ASJC Scopus subject areas

- Chemical Health and Safety
- Software
- Safety, Risk, Reliability and Quality
- Geometry and Topology