David EppsteinProfessor |
|
|
Research Interests |
Graph algorithms and computational geometry | |
| URLs | Departmental home page | |
| Research blog | ||
|
Research Abstract |
Prof. Eppstein has over 200 publications spanning a broad variety of topics in the design and analysis of algorithms, including - biological sequence comparison and RNA secondary structure inference - finite element mesh generation and optimal triangulation - constructing arrangements of lines and curves - data structures for maintaining information about changing graphs - clustering and hierarchical clustering - listing multiple nearly-optimal solutions to graph optimization problems - pattern matching in graphs - nearest neighbor and closest pair queries for geometric data - computational robust nonparametric statistics - parametric and bicriterion optimization - exponential time algorithms for NP-hard problems - spanning trees and low-distortion approximation of metrics by trees - graph coloring - reconstructing curves and surfaces from scattered data points - graph drawing and information visualization - folding and unfolding of surfaces - computational topology - computational complexity of puzzles and games - partial cubes and metric embedding of graphs - color spaces and optimization of color palettes - quasiconvex optimization and generalized low-dimensional linear programming - low-memory algorithms for high-bandwidth data streams |
|
| Publications | D. Eppstein, J.-C. Falmagne, and S. Ovchinnikov (2008). Media Theory: Interdisciplinary Applied Mathematics. Springer-Verlag. | |
| R. Beigel and D. Eppstein (2005). "3-coloring in time O(1.3289^n)", J. Algorithms 54(2): 168-204. | ||
| D. Eppstein and S. Muthukrishnan (2001). "Internet packet filter management and rectangle geometry", 12th ACM-SIAM Symp. Discrete Algorithms, pp. 827-835. | ||
| D. Eppstein (1999). "Finding the k shortest paths", SIAM J. Comput. 28(2): 652-673. | ||
| N. Amenta, M. Bern, and D. Eppstein (1998). "The Crust and the beta-skeleton: combinatorial curve reconstruction", Graphical Models and Image Processing 60/2(2): 125-135. | ||
| D. Eppstein, Z. Galil, G.F. Italiano, and A. Nissenzweig (1997). "Sparsification: a technique for speeding up dynamic graph algorithms", J. ACM 44(5): 669-696. | ||
| M. Bern, D. Eppstein, and J. Gilbert (1994). "Provably good mesh generation", J. Comp. Sys. Sci. 48: 384-409. | ||
| Link to this profile | http://www.faculty.uci.edu/profile.cfm?faculty_id=4679 | |
| Last updated | 10/26/2007 | |