Speaker:
Dr. Rex Dwyer, Computer Science, NCSU
Abstract: Convex hulls have been a staple of computational geometry since its debut as an indentifiable field with the publication of M. I. Shamos's dissertation in 1978. While attention has more frequently been focussed on the worst-case combinatorial complexity, some investigators have also considered average complexities for various input distributions.
Recently, Guibas et al., Albers and Roos, Agarwal et al. have considered the worst-case complexity for sets of *moving* points in Euclidean d-space. The strongest of these results show that the number of distinct topologies assumed by the convex hull is O(n^d) and Omega(n^floor(d/2 + 1)).
This talk will describe asymptotic analyses of the *average* combinatorial complexity of the convex hull for sets of independent random moving points in d-space. We define a random moving point to be one moving with unvarying velocity between a random source and an independent but identically distributed random destination during the time interval [0,1]. The results, which may be regarded as generalizations of recent results for the plane derived by Basch et al. can be summarized in the following three theorems:
Theorem 1: The expected combinatorial complexity of the convex hull of n random points moving between source and destination chosen from the uniform distribution on the unit ball in d-space is O(n^((d-1)/(d+1) log n) as n approaches infinity.
Theorem 2: The expected combinatorial complexity of the convex hull of n random points moving between source and destination chosen from the uniform distribution on the unit hypercube in d-space is O((log n)^d) as n approaches infinity.
Theorem 3: The expected combinatorial complexity of the convex hull of n random points moving between source and destination chosen from the standard normal distribution on d-space is O((log n)^(d/2)) as n approaches infinity.
For simplicity, the talk will focus on Theorem 3 in the plane. A full paper can be found at http://www.csc.ncsu.edu/eos/users/d/dwyer/www/movvor.ps
Short Bio: Rex A. Dwyer earned the AB in Germanic languages and the MS in computer science from Indiana University. After receiving the PhD from Carnegie-Mellon University in 1988, he joined the faculty of the Computer Science Department at NC State. Significant features of his recently-ended three-year term as Director of Graduate Programs were the implementation of the Master of Computer Science and BS/MS programs and a 40% increase in graduate enrollment.
Dr. Dwyer's research interests include computational geometry and computational methods in molecular biology.