Math @ Duke

Publications [#235397] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Katz, MJ; Sharir, M, Computing depth orders for fat objects and related problems,
Computational Geometry, vol. 5 no. 4
(1995),
pp. 187206, ISSN 09257721
(last updated on 2018/03/23)
Abstract: Let K be a set of n nonintersecting objects in 3space. A depth order of K, if it exists, is a linear order < of the objects in K such that if K, L ε{lunate} K and K lies vertically below L then K < L. We present a new technique for computing depth orders, and apply it to several special classes of objects. Our results include: (i) If K is a set of n triangles whose xyprojections are all 'fat', then a depth order for K can be computed in time O(n log5n). (ii) If K is a set of n convex and simplyshaped objects whose xyprojections are all 'fat' and their sizes are within a constant ratio from one another, then a depth order for K can be computed in time O(nλs 1 2(n) log4n), where s is the maximum number of intersections between the boundaries of the xyprojections of any pair of objects in K, and λs(n) is the maximum length of (n,s) DavenportSchinzel sequences. © 1995.


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

