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

Math @ Duke





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

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


Publications [#235563] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Aggarwal, A; Aronov, B; Kosaraju, SR; Schieber, B; Suri, S, Computing external farthest neighbors for a simple polygon, Discrete Applied Mathematics, vol. 31 no. 2 (1991), pp. 97-111, ISSN 0166-218X
    (last updated on 2017/12/15)

    Abstract:
    Let P be (the boundary of) a simple polygon with n vertices. For a vertex p of P, let φ{symbol}(p) be the set of points on P that are farthest from p, where the distance between two points is the length of the (Euclidean) shortest path that connects them without intersecting the interior of P. In this paper, we present an O(n log n) algorithm to compute a member of φ{symbol}(p) for every vertex p of P. As a corollary, the external diameter of P can also be computed in the same time. © 1991.

 

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

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