Computing many faces in arrangements of lines and segments

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. pn The main new idea is a simple randomized O(n log n) expected time algorithm for computing root n cells in an arrangement of n lines.
Publisher
SIAM PUBLICATIONS
Issue Date
1998-04
Language
ENG
Keywords

PLANAR PARTITION ALGORITHM; GEOMETRY; CONSTRUCTION; COMPLEXITY; NUMBER; EDGES; RAY

Citation

SIAM JOURNAL ON COMPUTING, v.27, no.2, pp.491 - 505

ISSN
0097-5397
DOI
10.1137/S009753979426616X
URI
http://hdl.handle.net/10203/323
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
1994-39.pdf(807.8 kB)Download
  • Hit : 591
  • Download : 219
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 17 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0