VORONOI DIAGRAMS OF LINES IN 3-SPACE UNDER POLYHEDRAL CONVEX DISTANCEFUNCTIONS

Authors
CHEW LP KEDEM K SHARIR M TAGANSKY B WELZL E
Citation
Lp. Chew et al., VORONOI DIAGRAMS OF LINES IN 3-SPACE UNDER POLYHEDRAL CONVEX DISTANCEFUNCTIONS, Journal of algorithms (Print), 29(2), 1998, pp. 238-255
Citations number
14
Categorie Soggetti
Mathematics,"Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms (Print) → ACNP
ISSN journal
01966774
Volume
29
Issue
2
Year of publication
1998
Pages
238 - 255
Database
ISI
SICI code
0196-6774(1998)29:2<238:VDOLI3>2.0.ZU;2-0
Abstract
The combinatorial complexity of the Voronoi diagram of n lines in thre e dimensions under a convex distance function induced by a polytope wi th a constant number of edges is shown to be O(n(2)alpha(n)log n), whe re alpha(n) is a slowly growing inverse of the Ackermann function. The re are arrangements of n lines where this complexity can be as large a s Omega(n(2)alpha(n)). (C) 1998 Academic Press.