Computing many faces in arrangements of lines and segments


Journal Article

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized O(n log n) expected time algorithm for computing √n cells in an arrangement of n lines.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; MatouĊĦek, J; Schwarzkopf, O

Published Date

  • January 1, 1998

Published In

Volume / Issue

  • 27 / 2

Start / End Page

  • 491 - 505

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/S009753979426616X

Citation Source

  • Scopus