# Computing depth orders for fat objects and related problems

Published

Journal Article

Let K be a set of n non-intersecting objects in 3-space. 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 xy-projections 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 simply-shaped objects whose xy-projections 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 xy-projections of any pair of objects in K, and λs(n) is the maximum length of (n,s) Davenport-Schinzel sequences. © 1995.

### Full Text

### Duke Authors

### Cited Authors

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

### Published Date

- January 1, 1995

### Published In

### Volume / Issue

- 5 / 4

### Start / End Page

- 187 - 206

### International Standard Serial Number (ISSN)

- 0925-7721

### Digital Object Identifier (DOI)

- 10.1016/0925-7721(95)00005-8

### Citation Source

- Scopus