enter search term and/or author name
Space-time tradeoffs for approximate nearest neighbor searching
Sunil Arya, Theocharis Malamatos, David M. Mount
Article No.: 1
Nearest neighbor searching is the problem of preprocessing a set of n point points in d-dimensional space so that, given any query point q, it is possible to report the closest point to q rapidly. In approximate nearest...
On the union of fat tetrahedra in three dimensions
Esther Ezra, Micha Sharir
Article No.: 2
We show that the combinatorial complexity of the union of n “fat” tetrahedra in 3-space (i.e., tetrahedra all of whose solid angles are at least some fixed constant) of arbitrary sizes, is O(n2+ϵ),...
Efficient and secure authenticated key exchange using weak passwords
Jonathan Katz, Rafail Ostrovsky, Moti Yung
Article No.: 3
Mutual authentication and authenticated key exchange are fundamental techniques for enabling secure communication over public, insecure networks. It is well known how to design secure protocols for achieving these goals when parties share...
Compressing and indexing labeled trees, with applications
Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, S. Muthukrishnan
Article No.: 4
Consider an ordered, static tree T where each node has a label from alphabet Σ. Tree T may be of arbitrary degree and shape. Our goal is designing a compressed storage scheme of T that supports basic navigational...