Partitioning arrangements of lines I: An efficient deterministic algorithm

Published

Journal Article

In this paper we consider the following problem: Given a set ℒ of n lines in the plane, partition the plane into O(r2) triangles so that no triangle meets more than O(n/r) lines of ℒ. We present a deterministic algorithm for this problem with O(nr log n/r) running time, where ω is a constant <3.33. © 1990 Springer-Verlag New York Inc.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK

Published Date

  • December 1, 1990

Published In

Volume / Issue

  • 5 / 1

Start / End Page

  • 449 - 483

Electronic International Standard Serial Number (EISSN)

  • 1432-0444

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/BF02187805

Citation Source

  • Scopus