 |
Franco P. Preparata
An Wang Professor of Computer ScienceContact Information
Box 1910Brown University
Providence, RI 02912
Email: franco at cs.brown.edu
Personal home page: http://www.cs.brown.edu/~franco/
Research Areas
| Computational Biology |
| Computational Geometry |
| Design and Analysis of Algorithms |
| Parallel Computing |
| Theory of Computation |
Research Themes
| Statistical Approaches |
Research Topics or Projects
| Sequencing by Hybridization |
| Homology Search |
| System Biology |
Courses Taught
Research Interests
Following early research in switching and coding, culminating in the discovery of the nonlinear Preparata codes, for the past three decades the focus of Franco Preparata’s research has been the design and analysis of algorithms in their most general connotation. With the remarkable evolution of computer technology, his research interests have been correspondingly evolving. He has been deeply interested in fundamental algorithms and data structures, VLSI computation and layout, and parallel algorithms.
Perhaps the most enduring interest has been computational geometry, a spin-off of algorithmic research aimed at the systematic investigation of methods for the most efficient solution of geometric problems. Geometric problems are ubiquitous in human activities. Sporadic, and frequently inefficient, computer solutions had been proposed before, but in the mid-1970s computational geometry emerged as a self-standing discipline targeted at this important area. The goal of computational geometry is to analyze the combinatorial structure of specific problems as the underpinning of efficient algorithms for their solution. The field burgeoned, and in the mid-1980s Prof. Preparata wrote a textbook on the subject that helped establish it in the instructional arena. Today an enormous body of geometric algorithms is known and this knowledge is increasingly indispensable in several applied areas such as geographic information systems, computer graphics, and computer-aided design and manufacturing. Within the last area, Prof. Preparata has also contributed to computational metrology—the assessment of the geometric quality of manufactured parts.
As another example of computer science interacting with other fields, today his main research focus is computational biology (also called "bioalgorithmics"), an emerging discipline that entails the development and use of mathematical and computer science techniques to solve problems in molecular biology. Since the discovery of the structure of DNA about 50 years ago and the digital underpinning of molecular biology, huge amounts of data have been generated in this field, making it necessary to resort to sophisticated computer science techniques for their analysis.
Selected Publications
Preparata, F., Zhang, L., and Choi, K. Quick, practical selection of effective seeds for homology search. Journal of Computational Biology 12, 9 (Oct 2005), 1137-1152. [ pdf ]
Preparata, F. Sequencing by Hybridization revisited: The analog-spectrum proposal. IEEE-ACM Transactions on Computational Biology and Bioinformatics 1, 1 (2004), 46-52. [ pdf ]
Codenotti, B., Leoncini, M., and Preparata, F. The role of arithmetic in fast parallel matrix inversion. Algorithmica 30, 4 (2001), 685-707. [ pdf ]
Boissonnat, J., and Preparata, F. Robust plane sweeps for intersecting segments. SIAM Journal on Computing 23, 5 (2000), 1401-1421. [ pdf ]
Preparata, F., and Upfal, E. Sequencing-by-hybridization at the information-theory bound: an optimal algorithm. In Proceedings of the Fourth Annual International Conference on Computational Molecular Biology (Tokyo, Apr 2000), pp. 245-253. [ pdf ]
Bilardi, G., and Preparata, F. Processor-time tradeoffs under bounded-speed message propagation: Part II, lowerbounds. Theory of Computing Systems 32 (1999), 531-559. [ pdf ]
Bilardi, G., and Preparata, F. Processor-time tradeoffs under bounded-speed message propagation: Part I, upper bounds. Theory of Computing Systems 30 (1997), 523-546. [ pdf ]
Apostolico, A., and Preparata, F. Data structures and algorithms for the string statistics problem. Algorithmica 15 (1996), 481-494.
Bilardi, G., and Preparata, F. P. Horizons of parallel computation. Journal of Parallel and Distributed Computing 27, 2 (1995), 172-182. [ pdf ]
Muller, D. E., and Preparata, F. P. Parallel restructuring and evaluation of expressions. Journal of Computer and System Sciences 44, 1 (1992), 43-62.
Zhou, D., Preparata, F. P., and Kang, S. M. Interconnection delay in very high-speed VLSI. IEEE Transactions on Circuits and Systems 28, 7 (Jul 1991), 779-790. [ pdf ]
Preparata, F. P., and Tamassia, R. Dynamic planar point location with optimal query time. Theoretical Computer Science 74 (1990), 95-114.
All publications by Franco P. Preparata
| Page Owner: Franco P. Preparata | Last Modified: Tue Sep 9 10:59:21 2008 |