COMPUTING MANY FACES IN ARRANGEMENTS OF LINES AND SEGMENTS

Authors
AGARWAL PK MATOUSEK J SCHWARZKOPF O
Citation
Pk. Agarwal et al., COMPUTING MANY FACES IN ARRANGEMENTS OF LINES AND SEGMENTS, SIAM journal on computing, 27(2), 1998, pp. 491-505
Citations number
21
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
27
Issue
2
Year of publication
1998
Pages
491 - 505
Database
ISI
SICI code
0097-5397(1998)27:2<491:CMFIAO>2.0.ZU;2-G
Abstract
We present randomized algorithms for computing many faces in an arrang ement of lines or of segments in the plane, which are considerably sim pler and slightly faster than the previously known ones. pn The main n ew idea is a simple randomized O(n log n) expected time algorithm for computing root n cells in an arrangement of n lines.