# David Eppstein - Publications

##

**Dynamic Euclidean minimum spanning trees and extrema of binary functions**.

D. Eppstein.

Tech. Rep. 92-05, ICS, UCI, 1992.

Tech. Rep. 92-88, ICS, UCI, 1992.

*Disc. Comp. Geom.* 13: 111–122, 1995.
Shows that bichromatic nearest neighbors can be maintained under point
insertion and deletion essentially as quickly as known solutions to the
post office problem, and that the
minimum spanning tree can be
maintained in the same time except for an additive O(sqrt *n*) needed for
solving the corresponding graph problem.
TR 92-88's title was actually "Fully dynamic maintenance of Euclidean
minimum spanning trees and maxima of decomposable functions".
TR 92-05's title left out the part about maxima; that version gave a slower
algorithm superseded by the result in 92-88.

Publications –
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
UC Irvine

Semi-automatically filtered
from a common source file.