Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235383] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK, Partitioning arrangements of lines I: An efficient deterministic algorithm, Discrete & Computational Geometry, vol. 5 no. 1 (1990), pp. 449-483, ISSN 0179-5376 [doi]
    (last updated on 2017/12/14)

    Abstract:
    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.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320