Math @ Duke

Publications [#235597] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Matoušek, J; Schwarzkopf, O, Computing many faces in arrangements of lines and segments,
SIAM Journal on Computing, vol. 27 no. 2
(1998),
pp. 491505
(last updated on 2018/12/12)
Abstract: 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

