He is best known for his 1985 book "Computational Geometry: An Introduction"[1] into which he blended salient parts of M. I. Shamos' doctoral thesis (Shamos appears as a co-author of the book). This book, which represents a snapshot of the disciplines as of 1985, has been for many years the standard textbook in the field, and has been translated into four foreign Languages (Russian, Japanese, Chinese, and Polish). He has made several contributions to the computational geometry, the most recent being the notion of "algorithmic degree" as a key feature to control robust implementations of geometric algorithms.
In addition, Preparata has worked in many other areas of, or closely related to, computer science.
His initial work was in coding theory, where he (independently and simultaneously) contributed the Berlekamp-Preparata codes (optimal convolution codes for burst-error correction) and the Preparata codes, the first known systematic class of nonlinear binary codes, with higher information content than corresponding linear BCH codes of the same length. Thirty years later these codes have been found relevant to quantum coding theory.
In 1967, he substantially contributed to a model of system-level fault diagnosis, known today as the PMC (Preparata-Metze-Chien) model, which is a main issue in the design of highly dependable processing systems. This model is still the object of intense research today (as attested by the literature).
Over the years, he was also active in research in parallel computation and VLSI theory. His 1979 paper (with Jean Vuillemin), still highly cited, presented the cube-connected-cycles (CCC), a parallel architecture that optimally emulates the hypercube interconnection. This interconnection was closely reflected in the architecture of the CM2 of Thinking Machines Inc., the first massive-parallel system in the VLSI era. His 1991 paper with Zhou and Kang on interconnection delays in VLSI was awarded the 1993 "Darlington Best Paper Award" by the IEEE Circuits and Systems Society. In the late nineties, (in joint work with G. Bilardi) he confronted the problem of the physical limitations (space and speed) of parallel computation, and formulated the conclusion that mesh connections are ultimately the only scalable massively parallel architectures.
More recently the focus of his research has been Computational Biology. Among other results, he contributed (with Eli Upfal) a novel approach to DNA Sequencing by Hybridization,[2] achieving sequencing lengths that are the square of what was previously known, which has attracted media coverage.
The unifying character of these results in diverse research areas is the methodological approach, based on the construction of precise mathematical models and the use of sophisticated mathematical techniques.
Preparata was born in Italy in December, 1935. He received a doctorate from the University of Rome, Italy in 1959. After a postdoctorate at CNR and several years of working in industry, he joined the faculty of the University of Illinois at Urbana-Champaign in 1965, where he achieved the rank of Professor in 1970. He stayed at the UIUC for many years, advising 16 Ph.D. students there. He received his Italian Libera Docenza in 1969. In 1991, Preparata moved from Illinois to Brown University where he has remained active in research, teaching, and student advising until his retirement at the end of 2013. He is the author (or co-author) of three books and nearly 250 articles. In 1997, the University of Padova awarded Preparata an honorary doctorate in Information Engineering. Preparata is an IEEE Fellow (1978), an ACM Fellow (1993), and was a Fellow of the Japan Society for the Advancement of Science.
Selected bibliography
Preparata, Franco P.; Metze, G.; Chien, R. T. (1967). "On the Connection Assignment Problem of Diagnosable Systems". IEEE Transactions on Electronic Computers. EC-16 (6): 848–854. doi:10.1109/PGEC.1967.264748. hdl:2142/74464.
Franco P. Preparata, Raymond T. Yeh, Introduction to Discrete Structures for Computer Science and Engineering (Addison-Wesley series in computer science and information processing), 1973, ISBN0-201-05968-1
Zhou, D.; Preparata, Franco P.; Kang, Sung Mo (1991). "Interconnection delay in very high-speed VLSI". IEEE Transactions on Circuits and Systems. 38 (7): 779–790. doi:10.1109/31.135749.
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation (TOC), formal language theory, the lambda calculus and type theory.
Charles Eric Leiserson is a computer scientist and professor at Massachusetts Institute of Technology (M.I.T.). He specializes in the theory of parallel computing and distributed computing.
In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of (multidimensional) rectangular ranges can be computed. Here, a d-dimensional rectangular range is defined to be a Cartesian product of d intervals of real numbers, which is a subset of Rd.
An isothetic polygon is a polygon whose alternate sides belong to two parametric families of straight lines which are pencils of lines with centers at two points. The most well-known example of isothetic polygons are rectilinear polygons, and the former term is commonly used as a synonym for the latter one.
In geometry, a star-shaped polygon is a polygonal region in the plane that is a star domain, that is, a polygon that contains a point from which the entire polygon boundary is visible.
In graph theory, the cube-connected cycles is an undirected cubic graph, formed by replacing each vertex of a hypercube graph by a cycle. It was introduced by Preparata & Vuillemin (1981) for use as a network topology in parallel computing.
In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points of line segments. It extends the Shamos–Hoey algorithm, a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of line segments with crossings, the Bentley–Ottmann algorithm takes time . In cases where , this is an improvement on a naïve algorithm that tests every pair of segments, which takes .
In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter of a set of points.
Michael Ian Shamos is an American mathematician, attorney, book author, journal editor, consultant and company director. He is the author of Computational Geometry, which was for many years the standard textbook in computational geometry, and is known for the Shamos–Hoey sweep line algorithm for line segment intersection detection and for the rotating calipers technique for finding the width and diameter of a geometric figure. His publications also include works on electronic voting, the game of billiards, and intellectual property law in the digital age.
In computational complexity theory, there is an open problem of whether some information about a sum of radicals may be computed in polynomial time depending on the input size, i.e., in the number of bits necessary to represent this sum. It is of importance for many problems in computational geometry, since the computation of the Euclidean distance between two points in the general case involves the computation of a square root, and therefore the perimeter of a polygon or the length of a polygonal chain takes the form of a sum of radicals.
Roberto Tamassia is an American Italian computer scientist, the Plastech Professor of Computer Science at Brown University, and served as the chair of the Brown Computer Science department from 2007 to 2014. His research specialty is in the design and analysis of algorithms for graph drawing, computational geometry, and computer security; he is also the author of several textbooks.
Information Processing Letters is a peer-reviewed scientific journal in the field of computer science, published by Elsevier. The aim of the journal is to enable fast dissemination of results in the field of information processing in the form of short papers. Submissions are limited to nine double-spaced pages.
Michael David Mitzenmacher is an American computer scientist working in algorithms. He is Professor of Computer Science at the Harvard John A. Paulson School of Engineering and Applied Sciences and was area dean of computer science July 2010 to June 2013. He also runs My Biased Coin, a blog about theoretical computer science.
Robert Tienwen Chien was an American computer scientist concerned largely with research in information theory, fault-tolerance, and artificial intelligence (AI), director of the Coordinated Science Laboratory (CSL) at the University of Illinois at Urbana–Champaign, and known for his invention of the Chien search and seminal contributions to the PMC model in system level fault diagnosis.
Witold Lipski Jr. was a Polish computer scientist, and an author of two books: Combinatorics for Programmers and (jointly with Wiktor Marek Combinatorial analysis. Lipski, jointly with his PhD student, Tomasz Imieliński, created foundations of the theory of incomplete information in relational databases.
Jean Vuillemin is a French computer scientist known for his work in data structures and parallel computing. He is a professor of computer science at the École normale supérieure (Paris).
In geometry, a slab is a region between two parallel lines in the Euclidean plane, or between two parallel planes in three-dimensional Euclidean space or between two hyperplanes in higher dimensions.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
