### Abstract

We consider the problem of bounding the complexity of the kth level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among other results, we prove a new bound, O(nk^{5/3}), on the complexity of the kth level in an arrangement of n planes in ℝ^{3}, or on the number of k-sets in a set of n points in three dimensions, and we show that the complexity of the kth level in an arrangement of n line segments in the plane is O(n-√kα(n/k)), and that the complexity of the kth level in an arrangement of n triangles in 3-space is O(n^{2}k^{5/6}α(n/k)).

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

Pages (from-to) | 315-331 |

Number of pages | 17 |

Journal | Discrete and Computational Geometry |

Volume | 19 |

Issue number | 3 |

DOIs | |

State | Published - Apr 1998 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'On levels in arrangements of lines, segments, planes, and triangles'. Together they form a unique fingerprint.

## Cite this

Agarwal, P. K., Aronov, B., Chan, T. M., & Sharir, M. (1998). On levels in arrangements of lines, segments, planes, and triangles.

*Discrete and Computational Geometry*,*19*(3), 315-331. https://doi.org/10.1007/PL00009348