Computing depth orders and related problems


Conference Paper

© 1994, Springer Verlag. All rights reserved. Let K: be a set of n non-intersecting objects in 3-space. A depth order of K, if exists, is a linear order < of the objects in K such that if K, L ε 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 xy-projections are all ‘fat’, then a depth order for K: can be computed in time O(n log6 n). (ii) If K: is a set of n convex and simply-shaped objects whose xy-projections are all ‘fat’ and their sizes axe within a constant ratio from one another, then a depth order for K: can be computed in time O(nλs1/2 12 (n)log4 n), where s is the maximum number of intersections between the xy-projections of the boundaries of any pair of objects in/C.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Katz, MJ; Sharir, M

Published Date

  • January 1, 1994

Published In

Volume / Issue

  • 824 LNCS /

Start / End Page

  • 1 - 12

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540582182

Digital Object Identifier (DOI)

  • 10.1007/3-540-58218-5_1

Citation Source

  • Scopus