Titlebook: SWAT ‘90; 2nd Scandinavian Wor John R. Gilbert,Rolf Karlsson Conference proceedings 1990 Springer-Verlag Berlin Heidelberg 1990 Algorithmus

WAG

平

Finding the , smallest spanning trees,akes time .(.log.(.)+..); for planar graphs this bound can be improved to .(.+..). We also show that the . best spanning trees for a set of points in the plane can be computed in time .(min(...+.log., ..+.log(.))). The . best orthogonal spanning trees in the plane can be found in time .(.log.+.loglo

DEVIL

The file distribution problem for processor networks,mentation problem can be reduced to the problem of finding a . coloring of the network with .+1 colors, where . is the degree of the network. We prove that a strong coloring with .+1 colors is possible for the .-dimensional hypercube if and only if .=2. − 1 for some .>0, for the .-dimensional torus

巧思

Translating polygons with applications to hidden surface removal,s such that, if the polygons are moved one by one to infinity in direction . according to this ordering, no collisions occur between the polygons. We show that, after .(. log .) preprocessing using .(.) space, it is possible to determine, for any given ., in .(log .) time whether such an ordering ex

FID

心胸狭窄

Graphics in flatland revisited,by a semi-infinite line rotating continuously around the viewpoint .. We show how to preprocess the set . in time .(.. · α(.)) where α(.) is a pseudo-inverse of Ackermann‘s function, so that the view from a given point in the plane can be computed in time .(. · 2.). Then we show how, with the same p

Unsaturated-Fat

Curmudgeon

尽忠

Expected behaviour analysis of AVL trees,t are not closed is presented. An inherent difficulty posed by the transformations necessary to keep the AVL tree balanced makes its analysis difficult when using fringe analysis methods. We derive a technique to cope with this difficulty obtaining the exact solution for fringe parameters even when

袖章

Lower bounds for monotonic list labeling,a structures, in the incremental evaluation of computational circuits and in the maintenance of dense sequential files. We prove, under a reasonable restriction on the algorithms, that Ω(. log..) relabelings are necessary when inserting . items into list monotonically labeled from a label space of s