------------------------------------------------------------------------------
Sliver Exudation (Herbert Edelsbrunner)

Abstract. A sliver in a 3-dimensional Delaunay triangulation
is a rather flat tetrahedron whose vertices lie close to a
plane, and the projection of the sliver to that plane is a
quadrangle.  We show that we can assign weights to the vertices
of the Delaunay triangulation such that the weighted Delaunay
triangulation (= regular = coherent triangulation) has no
sliver.
------------------------------------------------------------------------------
Universal Construction for the FKS Scheme (Chee Yap)

The problem of optimal static hashing was first solved in general by Fredman,
Komlos and Szemeredi (FKS). We introduce a new analysis of the FKS
construction, making a direct connection with the universality concepts of
Carter and Wegman. This leads to a more general universal construction for FKS 
schemes. Our result represents a new application of universal hashing: given
any strongly universal hash set H, one can construct a FKS scheme based on H.

We resolve a question first raised by the FKS paper: whether it is possible to 
use hash functions that avoid arithmetic on "large" numbers and the use of
primes. We provide a new class of hash functions to answer this in the
affirmative. This follows from an examination of the algebraic properties
which lead to universality in common has functions.

Our more general construction also has superior space complexity: under Yao's
cell model, we use  sqrt{15n} < 3.9n  cells which improves upon the original
6n cells. The space analysis uses a realistic cell model with parameters
r, t >= 1 (the case r = t = 1 is Yao's model).

We introduce the natural frameworks of weighted universal hashing. All results 
are proved in this setting. Two new transformations of weighted universal hash 
sets are given. Several applications of these universal constructions are
described.