Franco P. Preparata

Affiliations:
  • Brown University, Providence, USA


According to our database1, Franco P. Preparata authored at least 178 papers between 1964 and 2013.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 1995, "For significant research contributions in Computational Geometry, Parallel Algorithms, Theory of VLSI Layouts, Fault Diagnosis in Computer Systems, and Algebraic Coding Theory.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2013
On Contigs and Coverage.
J. Comput. Biol., 2013

2012
Accurate and precise aggregation counting.
J. Comput. Syst. Sci., 2012

2011
VLSI Computation.
Proceedings of the Encyclopedia of Parallel Computing, 2011

Steps Toward Unraveling a Vatican Cipher of the 1930s.
Cryptologia, 2011

2009
The evolving profile and role of computer science.
Sci. China Ser. F Inf. Sci., 2009

Self-matched Patterns, Golomb Rulers, and Sequence Reconstruction.
Proceedings of the Efficient Algorithms, 2009

2008
The unpredictable deviousness of models.
Theor. Comput. Sci., 2008

Spectrum-Based <i>De Novo</i> Repeat Detection in Genomic Sequences.
J. Comput. Biol., 2008

Algorithms for Location Estimation Based on RSSI Sampling.
Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2008

2007
A Novel Approach to the Detection of Genomic Approximate Tandem Repeats in the Levenshtein Metric.
J. Comput. Biol., 2007

2006
Beware of the Model: Reflections on Algorithmic Research.
Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

2005
Quick, Practical Selection of Effective Seeds for Homology Search.
J. Comput. Biol., 2005

Adaptive Control of Hybridization Noise in Dna Sequencing-by-hybridization.
J. Bioinform. Comput. Biol., 2005

2004
Sequencing-by-Hybridization Revisited: The Analog-Spectrum Proposal.
IEEE ACM Trans. Comput. Biol. Bioinform., 2004

DNA Sequencing by Hybridization Using Semi-Degenerate Bases.
J. Comput. Biol., 2004

2003
Sequencing by Hybridization by Cooperating Direct and Reverse Spectra.
J. Comput. Biol., 2003

Culling a Set of Points for Roundness or Cylindricity Evaluations.
Int. J. Comput. Geom. Appl., 2003

Circular Cylinders through Four or Five Points in Space.
Discret. Comput. Geom., 2003

2002
On the Control of Hybridization Noise in DNA Sequencing-by-Hybridization.
Proceedings of the Algorithms in Bioinformatics, Second International Workshop, 2002

Sequencing by hybridization using direct and reverse cooperating spectra.
Proceedings of the Sixth Annual International Conference on Computational Biology, 2002

2001
Generalized scans and tridiagonal systems.
Theor. Comput. Sci., 2001

The Role of Arithmetic in Fast Parallel Matrix Inversion.
Algorithmica, 2001

Enhanced Sequence Reconstruction with DNA Microarray Application.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

2000
Robust Plane Sweep for Intersecting Segments.
SIAM J. Comput., 2000

Sequencing-by-Hybridization at the Information-Theory Bound: An Optimal Algorithm.
J. Comput. Biol., 2000

Evaluating the cylindricity of a nominally cylindrical point set.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999
Processor - Time Tradeoffs under Bounded-Speed Message Propagation: Part II, Lower Bounds.
Theory Comput. Syst., 1999

Optimal Reconstruction of a Sequence from its Probes.
J. Comput. Biol., 1999

Further results on arithmetic filters for geometric predicates.
Comput. Geom., 1999

On the power of universal bases in sequencing by hybridization.
Proceedings of the Third Annual International Conference on Research in Computational Molecular Biology, 1999

1998
Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design.
SIAM J. Comput., 1998

A Probabilistic Analysis of the Power of Arithmetic Filters.
Discret. Comput. Geom., 1998

Checking the convexity of polytopes and the planarity of subdivisions.
Comput. Geom., 1998

1997
O(n)-Depth Modular Exponentiation Circuit Algorithm.
IEEE Trans. Computers, 1997

Practical Constructive Schemes for Deterministic Shared-Memory Access.
Theory Comput. Syst., 1997

Processor-Time Tradeoffs under Bounded-Speed Message Propagation: Part I, Upper Bounds.
Theory Comput. Syst., 1997

Evaluating Signs of Determinants Using Single-Precision Arithmetic.
Algorithmica, 1997

Checking the Convexity of Polytopes and the Planarity of Subdivisions (Extended Abstract).
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

1996
A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps.
SIAM J. Comput., 1996

Data Structures and Algorithms for the String Statistics Problem.
Algorithmica, 1996

Robustness in Geometric Algorithms.
Proceedings of the Applied Computational Geormetry, 1996

Robust Proximity Queries in Implicit Voronoi Diagrams.
Proceedings of the 8th Canadian Conference on Computational Geometry, 1996

1995
Work-Preserving Speed-Up of Parallel Matrix Computations.
SIAM J. Comput., 1995

Horizons of Parallel Computation.
J. Parallel Distributed Comput., 1995

Motion planning of legged robots: the spider robot problem.
Int. J. Comput. Geom. Appl., 1995

A Time-Optimal Parallel Algorithm for Three-Dimensional Convex Hulls.
Algorithmica, 1995

Lower Bounds to Processor-Time Tradeoffs under Bounded-Speed Message Propagation.
Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Generalized Scans and Tri-Diagonal Systems.
Proceedings of the STACS 95, 1995

Upper Bounds to Processor-Time Tradeoffs under Bounded-Speed Message Propagation.
Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, 1995

Should Amdahl's Law Be Repealed? (Abstract).
Proceedings of the Algorithms and Computation, 6th International Symposium, 1995

Evaluation of a New Method to Compute Signs of Determinants.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

O(n)-depth circuit algorithm for modular exponentiation.
Proceedings of the 12th Symposium on Computer Arithmetic (ARITH-12 '95), 1995

1994
Widest-Corridor Problems.
Nord. J. Comput., 1994

1993
A Simplified Technique for Hidden-Line Elimination in Terrains.
Int. J. Comput. Geom. Appl., 1993

On O(sqrt(n))-Worst-Case-Time Solution to the Granularity Problem.
Proceedings of the STACS 93, 1993

A Practical Constructive Scheme for Deterministic Shared-Memory Access.
Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

An NC Parallel 3D Convex Hull Algorithm.
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

On the Manhattan and knock-knee Routing Models.
Proceedings of the Algorithmic Aspects of VLSI Layout, 1993

1992
Efficient Point Location in a Convex Spatial Cell-Complex.
SIAM J. Comput., 1992

Parallel Restructuring and Evaluation of Expressions.
J. Comput. Syst. Sci., 1992

The parallel 3D convex hull problem revisited.
Int. J. Comput. Geom. Appl., 1992

Output-Sensitive Generation of the Perspective View of Isothetic Parallelepipeds.
Algorithmica, 1992

Supereffective Slow-Down of Parallel Computations.
Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992

Frontiers of Parallel Computing.
Proceedings of the Parallel Architectures and Their Efficient Use, 1992

Motion planning for spider robots.
Proceedings of the 1992 IEEE International Conference on Robotics and Automation, 1992

Stable Placements for Spider Robots.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

1991
Deterministic P-RAM Simulation with Constant Redundancy
Inf. Comput., May, 1991

Inverting a Vandermonde Matrix in Minimum Parallel Time.
Inf. Process. Lett., 1991

Computing the union of 3-colored triangles.
Int. J. Comput. Geom. Appl., 1991

An Optimal Algorithm for the Boundary of a Cell in a Union of Rays-Corrigendum.
Algorithmica, 1991

1990
Computation of the axial view of a set of isothetic parallelepipeds.
ACM Trans. Graph., 1990

Dynamic Planar Point Location with Optimal Query Time.
Theor. Comput. Sci., 1990

Practical Cellular Dividers.
IEEE Trans. Computers, 1990

Characterization of Associative Operations with Prefix Circuits of Constant Depth and Linear Size.
SIAM J. Comput., 1990

Tetrahedrizing Point Sets in Three Dimensions.
J. Symb. Comput., 1990

Planar Point Location Revisited (Review Paper).
Int. J. Found. Comput. Sci., 1990

Dynamic Maintenance of Planar Digraphs, with Applications.
Algorithmica, 1990

An Optimal Algorithm for the Boundary of a Cell in a Union of Rays.
Algorithmica, 1990

1989
Holographic dispersal and recovery of information.
IEEE Trans. Inf. Theory, 1989

Fully Dynamic Point Location in a Monotone Subdivision.
SIAM J. Comput., 1989

Size-time complexity of Boolean networks for prefix computations.
J. ACM, 1989

Parallel Batched Planar Point Location on the CCC.
Inf. Process. Lett., 1989

Efficient Spatial Point Location (Extended Abstract).
Proceedings of the Algorithms and Data Structures, 1989

On the Boundary of a Union of Rays.
Proceedings of the STACS 89, 1989

A Heuristic for Channel Routing.
Proceedings of the Foundations of Data Organization and Algorithms, 1989

1988
Minimum Polygonal Separation
Inf. Comput., June, 1988

Tetrahedrizing Point Sets in Three Dimensions.
Proceedings of the Symbolic and Algebraic Computation, 1988

Interconnection delay in very high-speed VLSI.
Proceedings of the Computer Design: VLSI in Computers and Processors, 1988

Planar Point Location Revisited (A Guided Tour of a Decade of Research).
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1988

Fully Dynamic Techniques for Point Location and Transitive Closure in Planar Structures (Extended Abstract)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987
Area-Time Optimal Division for T=Omega((log n)^1+ epsilon)
Inf. Comput., March, 1987

Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones.
SIAM J. Comput., 1987

A Unified Approach to Layout Wirability.
Math. Syst. Theory, 1987

A bottom-up layout technique based on two-rectangle routing.
Integr., 1987

Toward a switching theory of CMOS circuits.
Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, 1987

1986
Routing through a rectangle.
J. ACM, 1986

New Upper Bounds for Neighbor Searching
Inf. Control., 1986

Halfspace Range Search: An Algorithmic Application of k-Sets.
Discret. Comput. Geom., 1986

Channel Routing in Knock-Knee Mode: Simplified Algorithms and Proofs.
Algorithmica, 1986

Area-Time Lower-Bound Techniques with Applications to Sorting.
Algorithmica, 1986

Area-time Optimal Division for T=Omega(log n)<sup>1+epsilon</sup>
Proceedings of the STACS 86, 1986

Digital Filtering in VLSI.
Proceedings of the VLSI Algorithms and Architectures, 1986

1985
A Minimum Area VLSI Network for <i>O</i>(log <i>n</i>) Time Sorting.
IEEE Trans. Computers, 1985

Structural Properties of the String Statistics Problem.
J. Comput. Syst. Sci., 1985

The VLSI Optimality of the AKS Sorting Network.
Inf. Process. Lett., 1985

The Influence of Key Length on the Area-Time Complexity of Sorting.
Proceedings of the Automata, 1985

Computational Geometry - An Introduction.
Texts and Monographs in Computer Science, Springer, ISBN: 978-1-4612-1098-6, 1985

1984
Optimal Three-Layer Channel Routing.
IEEE Trans. Computers, 1984

Computational Geometry - A Survey.
IEEE Trans. Computers, 1984

An Architecture for Bitonic Sorting with Optimal VLSI Performance.
IEEE Trans. Computers, 1984

Euclidean shortest paths in the presence of rectilinear barriers.
Networks, 1984

A Minimum Area VLSI Network for O(log n) Time Sorting
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

VLSI Algorithms and Architectures.
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

1983
Optimal Off-Line Detection of Repetitions in a String.
Theor. Comput. Sci., 1983

A Mesh-Connected Area-Time Optimal VLSI Multiplier of Large Integers.
IEEE Trans. Computers, 1983

Area-Time Optimal VLSI Circuits for Convolution.
IEEE Trans. Computers, 1983

Optimal Three-Dimensional VLSI Layouts.
Math. Syst. Theory, 1983

Area-Time Optimal VLSI Integer Multiplier with Minimum Computation Time
Inf. Control., 1983

1982
Corrigendum: Finding the Contour of a Union of Iso-Oriented Rectangles.
J. Algorithms, 1982

An Improved Algorithm for the Rectangle Enclosure Problem.
J. Algorithms, 1982

Plane-Sweep Algorithms for Intersecting Geometric Figures.
Commun. ACM, 1982

Approximation Algorithms for Convex Hulls.
Commun. ACM, 1982

Stabbing Line Segments.
BIT, 1982

Three Layers Are Enough
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981
A New Approach to Planar Point Location.
SIAM J. Comput., 1981

Erratum: Finding the Contour of a Union of Iso-Oriented Rectangles.
J. Algorithms, 1981

Segments, Rectangles, Contours.
J. Algorithms, 1981

Testing a Simple Polygon for Monotonicity.
Inf. Process. Lett., 1981

The Cube-Connected Cycles: A Versatile Network for Parallel Computation.
Commun. ACM, 1981

Efficient Algorithms for Finding Maximum Matchings in Convex Bipartite Graphs and Related Problems.
Acta Informatica, 1981

Euclidian Shortest Paths in the Presence of Parallel Rectilinear Barriers.
Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG '81), 1981

Area-Time Optimal VLSI Networks for Computing Integer Multiplications and Discrete Fourier Transform.
Proceedings of the Automata, 1981

1980
Finding the Contour of a Union of Iso-Oriented Rectangles.
J. Algorithms, 1980

Area-Time Optimal VLSI Networks for Multiplying Matrices.
Inf. Process. Lett., 1980

1979
Finding the Intersection of n Half-Spaces in Time O(n log n).
Theor. Comput. Sci., 1979

A Note on Locating a Set of Points in a Planar Subdivision.
SIAM J. Comput., 1979

An Optimal Algorithm for Finding the Kernel of a Polygon.
J. ACM, 1979

An Optimal Real-Time Algorithm for Planar Convex Hulls.
Commun. ACM, 1979

The Cube-Connected-Cycles: A Versatile Network for Parallel Computation (Extended Abstract)
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
Finding the Intersection of two Convex Polyhedra.
Theor. Comput. Sci., 1978

The Densest Hemisphere Problem.
Theor. Comput. Sci., 1978

Spectrum Shaping with Alphabetic Codes with Finite Autocorrelation Sequence.
IEEE Trans. Commun., 1978

New Parallel-Sorting Schemes.
IEEE Trans. Computers, 1978

An Improved Parallel Processor Bound in Fast Matrix Inversion.
Inf. Process. Lett., 1978

The All Nearest-Neighbor Problem for Convex Polygons.
Inf. Process. Lett., 1978

Triangulating a Simple Polygon.
Inf. Process. Lett., 1978

Improved Time and Space Bounds for Boolean Matrix Multiplication.
Acta Informatica, 1978

1977
Reduction of Depth of Boolean Networks with a Fan-In Constraint.
IEEE Trans. Computers, 1977

Location of a Point in a Planar Subdivision and Its Applications.
SIAM J. Comput., 1977

Convex Hulls of Finite Sets of Poin ts in Two and Three Dimensions.
Commun. ACM, 1977

The Medial Axis of a Simple Polygon.
Proceedings of the Mathematical Foundations of Computer Science 1977, 1977

1976
Corrigendum: A Fast Stable Sorting Algorithm with Absolutely Minimum Storage.
Theor. Comput. Sci., 1976

Efficient Parallel Evaluation of Boolean Expression.
IEEE Trans. Computers, 1976

Restructuring of Arithmetic Expressions For Parallel Evaluation.
J. ACM, 1976

Storage for Consecutive Retrieval.
Inf. Process. Lett., 1976

1975
A Fast Stable Sorting Algorithm with Absolutely Minimum Storage.
Theor. Comput. Sci., 1975

Bounds to Complexities of Networks for Sorting and for Switching.
J. ACM, 1975

On Finding the Maxima of a Set of Vectors.
J. ACM, 1975

The Time Required to Evaluate Division-Free Arithmetic Expressions.
Inf. Process. Lett., 1975

1974
Difference-preserving codes.
IEEE Trans. Inf. Theory, 1974

1972
Universal Logic Modules of a New Type.
IEEE Trans. Computers, 1972

Continuously Valued Logic.
J. Comput. Syst. Sci., 1972

An approach to artificial nonsymbolic cognition.
Inf. Sci., 1972

1971
Some Results in the Theory of Arithmetic Codes
Inf. Control., October, 1971

On the Delay Required to Realize Boolean Functions.
IEEE Trans. Computers, 1971

On the Design of Universal Boolean Functions.
IEEE Trans. Computers, 1971

1970
A new look at the Golay (23, 12) code (Corresp.).
IEEE Trans. Inf. Theory, 1970

R70-28 A Note on Definite Stochastic Sequential Machines.
IEEE Trans. Computers, 1970

Generation of Near-Optimal Universal Boolean Functions.
J. Comput. Syst. Sci., 1970

1968
A Class of Optimum Nonlinear Double-Error-Correcting Codes
Inf. Control., October, 1968

Erratum, "Weight and Distance Structure of Nordstrom-Robinson Quadratic Code"
Inf. Control., August, 1968

Convolutional Transformation and Recovery of Binary Sequences.
IEEE Trans. Computers, 1968

Weight and Distance Structure of Nordstrom-Robinson Quadratic Code
Inf. Control., 1968

1967
On the Connection Assignment Problem of Diagnosable Systems.
IEEE Trans. Electron. Comput., 1967

1966
Convolutional Transformations of Binary Sequences: Boolean Functions and Their Resynchronizing Properties.
IEEE Trans. Electron. Comput., 1966

1965
On the Realizability of Special Classes of Autonomous Sequential Networks.
IEEE Trans. Electron. Comput., 1965

1964
A synthesis procedure of recurrent codes (Corresp.).
IEEE Trans. Inf. Theory, 1964

State-Logic Relations for Autonomous Sequential Networks.
IEEE Trans. Electron. Comput., 1964


  Loading...