Vertical ray shooting and computing depth orders of fat objects

M. Berg, de; C.M. Gray

Vertical ray shooting and computing depth orders of fat objects

M. Berg, de, C.M. Gray

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

8 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Proceedings 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA, Miami FL, USA, January 22-24, 2006)
Publisher	Association for Computing Machinery, Inc
Pages	494-503
ISBN (Print)	0-89871-605-5
Publication status	Published - 2006

Cite this

@inproceedings{074a44abf61e48949aa585630c024c2d,

title = "Vertical ray shooting and computing depth orders of fat objects",

abstract = "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.",

author = "{Berg, de}, M. and C.M. Gray",

year = "2006",

language = "English",

isbn = "0-89871-605-5",

pages = "494--503",

booktitle = "Proceedings 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA, Miami FL, USA, January 22-24, 2006)",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

}

Vertical ray shooting and computing depth orders of fat objects. / Berg, de, M.; Gray, C.M.
Proceedings 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA, Miami FL, USA, January 22-24, 2006). Association for Computing Machinery, Inc, 2006. p. 494-503.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Vertical ray shooting and computing depth orders of fat objects

AU - Berg, de, M.

AU - Gray, C.M.

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

UR - http://doi.acm.org/10.1145/1109557.1109612

M3 - Conference contribution

SN - 0-89871-605-5

SP - 494

EP - 503

BT - Proceedings 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA, Miami FL, USA, January 22-24, 2006)

PB - Association for Computing Machinery, Inc

ER -

Vertical ray shooting and computing depth orders of fat objects

Abstract

Other files and links

Fingerprint

Cite this