Vertical ray shooting and computing depth orders of fat objects

M. Berg, de, C.M. Gray

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

8 Citations (Scopus)


We present new results for three problems dealing with a set P of n convex constant-complexity fat polyhedra in 3-space. (i) We describe a data structure for vertical ray shooting in P that has O(log2 n) query time and uses O(n log2 n) storage. (ii) We give an algorithm to compute in O(n log3 n) time a depth order on P, if it exists. (iii) We give an algorithm to verify in O(n log4 n) time whether a given order on P is a valid depth order. All three results improve on previous results.
Original languageEnglish
Title of host publicationProceedings 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA, Miami FL, USA, January 22-24, 2006)
PublisherAssociation for Computing Machinery, Inc
ISBN (Print)0-89871-605-5
Publication statusPublished - 2006


Dive into the research topics of 'Vertical ray shooting and computing depth orders of fat objects'. Together they form a unique fingerprint.

Cite this