KP: Quick, practical selection of effective seeds for homology search (2009)
Franco P. Preparata, Louxin Zhang, Kwok Pui Choi
It has been observed that in homology search gapped seeds have better sensitivity than ungapped ones for the same cost (weight). In this paper, we propose a probability leakage model (a dissipative...
Spectrum-Based De Novo Repeat Detection in Genomic Sequences (2009)
Huy Hoang Do, Kwok Pui Choi, Franco P. Preparata, Wing Kin Sung, Louxin Zhang
A novel approach to the detection of genomic repeats is presented in this paper. The technique, dubbed SAGRI (Spectrum Assisted Genomic Repeat Identifier), is based on the spectrum (set of sequence...
Nordic Journal of Computing 1(1994), 231–245. WIDEST-CORRIDOR PROBLEMS (2008)
Ravi Janardan, Franco P. Preparata
Abstract. A k-dense corridor through a finite set, S, of n points in the plane is the open region of the plane that is bounded by two parallel lines that intersect the convex hull of S and such that...
[30] Raj Reddy, “Foundations and Grand Challenges of Artificial Intelligence, ” AI Magazine, (2008)
Stephen M. Omohundro, Building Boxtrees, International Computer Science, Franco P. Preparata, Michael Ian Shamos, Computational Geometry, ...
On Circular Cylinders through Four or Five Points in Space (2008)
Olivier Devillers, Bernard Mourrain, Franco P. Preparata, Philippe Trebuchet
this paper is the analysis of circular cylinders through sets of points in three dimensions. This investigation has a number of motivations. Clearly, if a cylinder of radius R and direction t passes...
Olivier Devillers, Franco P. Preparata, Roberto Tamassia
This paper studies the problem of verifying the correctness of geometric structures. In particular, we design optimal checkers for convex polytopes in two and higher dimensions, and for various types...
Generalized Scans and Tri-Diagonal Systems (2007)
Paul F. Fischer, Franco P. Preparata, John E. Savage
Motivated by the analysis of known parallel techniques for the solution of linear tridiagonal system, weintroduce generalized scans, a class of recursively de#ned lengthpreserving,...
Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Roberto Tamassia, Roberto Tamassia, ...
apport de recherche
Franco P. Preparata, Jeffrey Scott Vitter
In this paper we give a practical and efficient output-sensitive algorithm for constructing the display of a polyhedral terrain. It runs in O((d + n) log 2 n) time and uses O(nff(n)) space, where d...
Roberto Tamassia, Pankaj K. Agarwal, Nancy Amato, Danny Z. Chen, David Dobkin, ...
The proposed research will be in the area of applied algorithms in both the sequential and parallel domains. The focus of this work will be on the design and testing of realistic algorithms for...
Francis Avnaim, Jean-daniel Boissonnat, Olivier Devillers, Franco P. Preparata, Mariette Yvinec
signs of determinants using single-precision arithmetic
Jean-daniel Boissonnat, Olivier Devillers, Franco P. Preparata
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can...
Francis Avnaim, Francis Avnaim, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Olivier Devillers, Olivier Devillers, ...
image et vision apport de recherche 1994 Evaluating signs of determinants using single-precision arithmetic
Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Thème Génie Logiciel, Projet Prisme, ...
apport
Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Thème Génie Logiciel, Projet Prisme
apport de recherche Evaluating the cylindricity of a nominally cylindrical point set (draft)
Motion Planning of Legged Robots: (2007)
Unite De Recherche, Inria-sophia Antipolis, Et En Automatique, Route Des Lucioles, Jean-daniel Boissonnat, ...
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can...
DNA sequencing by hybridization using semi-degenerate bases (2004)
Franco P. Preparata, John S. Oliver
One way to enhance the performance of hybridization microarrrays for DNA de novo sequencing is the use of probing patterns with gaps of unsampled positions. Ideally, such gaps could be realized by...
Sequencing-by-Hybridization Revisited: (2004)
All published approaches to DNA sequencing by hybridization (SBH) consist of the biochemical acquisition of the spectrum of a target sequence (the set of its subsequences conforming to a given...
On circular cylinders by four or five points in space (2003)
Olivier Devillers, Bernard Mourrain, Franco P. Preparata, Philippe Trebuchet
Restructuring of Arithmetic Expressions for Parallel Evaluation. (2002)
Muller,David E., Preparata,Franco P.
Let E be an arithmetic expression involving n variables, each of which appears just once, and the possible operations of addition, multiplication and division. Although other cases are considered,...
Finding the Contour of a Union of Iso-Oriented Rectangles. (2002)
Let R(1),...,R(m) be rectangles on the plane with sides parallel to the coordinate axes. An algorithm is described to find the contour of F = R(1) U ... U R(m) in o(mlogm + plog(2 sq m/p)) time,...
Area-Time Optimal VLSI Networks Based on the Cube-Connected-Cycles. (2002)
Preparata, Franco P., Vuillemin, Jean E.
This report presents designs for VLSI circuits computing Cyclic Shifts, Discrete Fourier Transforms, and Integer Multiplication, all based on a machine architecture, the Cube-Connected-Cycles CCC,...
The Cube-Connected-Cycles: A Versatile Network for Parallel Computation. (2002)
Preparata,Franco P., Vuillemin,Jean
We introduce an interconnection pattern of processing elements, the cube-connected-cycles (CCC), which can be used as a general purpose parallel processor. Because its design complies with present...
Preparata,Franco P., Vuillemin,Jean E.
This report consists of two papers describing networks for parallel matrix operations. In the first paper, Area-time optimal VLSI (Very Large Scale Integration) networks for multiplying matrices, we...
Segments, Rectangles, Contours. (2002)
Two sets H and V of horizontal and vertical segments, respectively, determine a subdivision M of the plane into regions. A nontrivial region is one whose boundary contains an end-portion of nonzero...
Area-Time Lower-Bound Techniques with Application to Sorting. (2002)
Bilardi,Gianfranco, Preparata,Franco P.
The area-time complexity of VLSI(Very Large Scale Integration) computations is constrained by the flow and the storage of information in the two-dimensional chip. We study here the information...
The VLSI Optimality of the AKS Sorting Network. (2002)
Bilardi,Gianfranco, Preparata,Franco P.
Ajtai, Komlos, and Szemeredi recently proposed a sorting network of O(nlogn) comparators and O(logn) depth. Their construction is of great theoretical interest, for it shows that O(nlogn) comparisons...
Sequencing by hybridization using direct and reverse cooperating spectra (2002)
Samuel A. Heath, Franco P. Preparata, Joel Young
DNA sequencing by hybridization, proposed about a decade ago as an alternative to standard electrophoresis-based sequencing techniques, is relevant not only to sequencing per se but also to...
On circular Cylinders by Four or Five Points in Space (2001)
Devillers, Olivier, Mourrain, Bernard, Preparata, Franco P., Trebuchet, Philippe
We are interested in computing effectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a fix radius and...
Culling a Set of Points for Roundness or Cylindricity Evaluations (2001)
Devillers, Olivier, Preparata, Franco P.
Roundness and cylindricity evaluations are among the most important problems in computational metrology, and are based on sets of surface measurements (input data points). A recent approach to such...
On circular Cylinders by Four or Five Points in Space (2001)
Devillers, Olivier, Mourrain, Bernard, Preparata, Franco P., Trebuchet, Philippe
We are interested in computing effectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a fix radius and...
Culling a Set of Points for Roundness or Cylindricity Evaluations (2001)
Devillers, Olivier, Preparata, Franco P.
Roundness and cylindricity evaluations are among the most important problems in computational metrology, and are based on sets of surface measurements (input data points). A recent approach to such...
On circular Cylinders by Four or Five Points in Space (2001)
Devillers, Olivier, Mourrain, Bernard, Preparata, Franco P., Trebuchet, Philippe
We are interested in computing effectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a fix radius and...
Culling a Set of Points for Roundness or Cylindricity Evaluations (2001)
Devillers, Olivier, Preparata, Franco P.
Roundness and cylindricity evaluations are among the most important problems in computational metrology, and are based on sets of surface measurements (input data points). A recent approach to such...
Culling a Set of Points For Roundness or Cylindricity Evaluations (2001)
Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata
Roundness and cylindricity evaluations are among the most important problems in computational metrology, and are based on sets of surface measurements (input data points). A recent approach to such...
On Circular Cylinders by Four or Five Points in Space (2001)
Unit Inria, Sophia Antipolis, Olivier Devillers, Olivier Devillers, Bernard Mourrain, Bernard Mourrain, ...
We are interested in computing eoeectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a x radius and with...
Sequencing-by-Hybridization at the Information-Theory Bound: An Optimal Algorithm (2000)
Franco P. Preparata, Eli Upfal
In a recent paper (Preparata et al., 1999) we introduced a novel probing scheme for DNA sequencing by hybridization (SBH). The new gapped-probe scheme combines natural and universal bases in a...
Sequencing-by-Hybridization at the Information-Theory Bound: An Optimal Algorithm (2000)
Franco P. Preparata, Eli Upfal
In a recent paper (Preparata et al., 1999) we introduced a novel probing scheme for DNA sequencing by hybridization (SBH). The new gapped-probe scheme combines natural and universal bases in a...
Further Results on Arithmetic Filters for Geometric Predicates (1999)
Devillers, Olivier, Preparata, Franco P.
An efficient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of...
A Probabilistic Analysis of the Power of Arithmetic Filters (1999)
Devillers, Olivier, Preparata, Franco P.
The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...
Evaluating the Cylindricity of a Nominally Cylindrical Point Set (Draft) (1999)
Devillers, Olivier, Preparata, Franco P.
The minimum zone cylinder of a set of points in three dimensions is the cylindric crown defined by a pair of coaxial cylinders with minimal radial separation (width). In the context of tolerancing...
Evaluating the Cylindricity of a Nominally Cylindrical Point Set (Draft) (1999)
Devillers, Olivier, Preparata, Franco P.
The minimum zone cylinder of a set of points in three dimensions is the cylindric crown defined by a pair of coaxial cylinders with minimal radial separation (width). In the context of tolerancing...
Evaluating the Cylindricity of a Nominally Cylindrical Point Set (Draft) (1999)
Devillers, Olivier, Preparata, Franco P.
The minimum zone cylinder of a set of points in three dimensions is the cylindric crown defined by a pair of coaxial cylinders with minimal radial separation (width). In the context of tolerancing...
Further results on arithmetic filters for geometric predicates (1999)
Olivier Devillers, Franco P. Preparata
An eOEcient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of lters....
Optimal Reconstruction of a Sequence From its Probes (1999)
Alan M. Frieze, Franco P. Preparata, Eli Upfal
An important combinatorial problem, motivated by DNA sequencing in molecular biology, is the reconstruction of a sequence over a small finite alphabet from the collection of its probes (the sequence...
Evaluating The Cylindricity Of A Nominally Cylindrical Point Set (1999)
Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Projet Prisme
The minimum zone cylinder of a set of points in three dimensions is the cylindric crown dened by a pair of coaxial cylinders with minimal radial separation (width). In the context of tolerancing...
ON THE DELAY REQUIRED TO REALIZE BOOLEAN FUNCTIONS, (1998)
Preparata,Franco P., Muller,David E.
Using as logic modules two-input one-output arbitrary logic gates, this paper considers the problem of the longest chain (Number of levels) in a tree-type interconnection realizing a Boolean function...
AN APPROACH TO ARTIFICIAL NONSYMBOLIC COGNITION, (1998)
Preparata,Franco P., Ray,Sylvian R.
The paper describes an approach to the artificial recognition of events of a nonsymbolic nature, such as the bidimensional perspective views of scenes of the everyday world. Scenes are presented as...
Bounds to Complexities of Networks for Sorting and for Switching, (1998)
Muller,David E., Preparata,Franco P.
A network which sorts n numbers when used to sort numbers of only two sizes, 0 and 1, can be regarded as forming the n frontal (unate) symmetric boolean functions of n arguments. When sorting...
Applicable and Robust Geometric Computing (1998)
Preparata, Franco P., Agarwal, Pankaj K., Tamassia, Roberto, Vitter, Jeffrey S., Goodrich, Michael T.
This research project is aimed at aimed at facilitating an effective technology transfer from computational geometry to the various applied fields to which it is relevant. Our technical contributions...
Checking the Convexity of Polytopes and the Planarity of Subdivisions (1998)
Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco P., Tamassia, Roberto
This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...
Further Results on Arithmetic Filters for Geometric Predicates (1998)
Devillers, Olivier, Preparata, Franco P.
An efficient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of...
Checking the Convexity of Polytopes and the Planarity of Subdivisions (1998)
Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco P., Tamassia, Roberto
This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...
Further Results on Arithmetic Filters for Geometric Predicates (1998)
Devillers, Olivier, Preparata, Franco P.
An efficient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of...
Checking the Convexity of Polytopes and the Planarity of Subdivisions (1998)
Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco P., Tamassia, Roberto
This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...
Further Results on Arithmetic Filters for Geometric Predicates (1998)
Devillers, Olivier, Preparata, Franco P.
An efficient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of...
A Probabilistic Analysis of the Power of Arithmetic Filters (1998)
Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Projet Prisme
The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...
A Probabilistic Analysis of the Power of Arithmetic Filters (1998)
Franco P. Preparata, Olivier Devillers, Olivier Devillers, Franco P. Preparata
The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...
Further Results on Arithmetic Filters for Geometric Predicates (1998)
Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Adresses O. Devillers
An eOEcient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of lters....
Robust Plane Sweep for Intersecting Segments (1997)
Boissonnat, Jean-Daniel, Preparata, Franco P.
In this paper, we reexamine in the framework of robust computation the Bentley-Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being...
Robust Plane Sweep for Intersecting Segments (1997)
Boissonnat, Jean-Daniel, Preparata, Franco P.
In this paper, we reexamine in the framework of robust computation the Bentley-Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being...
Robust Plane Sweep for Intersecting Segments (1997)
Boissonnat, Jean-Daniel, Preparata, Franco P.
In this paper, we reexamine in the framework of robust computation the Bentley-Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being...
A Probabilistic Analysis of the Power of Arithmetic Filters (1997)
Olivier Devillers, Franco P. Preparata
The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...
Robust Plane Sweep for Intersecting Segments (1997)
Unit Inria, Sophia Antipolis, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Franco P. Preparata, Franco P. Preparata
In this paper, we reexamine in the framework of robust computation the Bentley-Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being...
Checking the Convexity of Polytopes and the Planarity of Subdivisions (1997)
Franco Preparata, Olivier Devillers, Olivier Devillers, Franco P. Preparata, Roberto Tamassia, ...
This paper considers the problem of verifying the correctness of geometric structures. In particular, we design optimal checkers for convex polytopes in two and higher dimensions, and for various...
Evaluating Signs of Determinants Using Single-Precision Arithmetic (1997)
Jean-daniel Boissonnat, Francis Avnaim, Francis Avnaim, Olivier Devillers, Olivier Devillers, Franco P. Preparata, ...
We propose a method to evaluate signs of 2 × 2 and 3 × 3 determinants with b-bit integer entries using only b and (b + 1)-bit arithmetic respectively. This algorithm has numerous...
A Probabilistic Analysis of the Power of Arithmetic Filters (1996)
Devillers, Olivier, Preparata, Franco P.
The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...
A Probabilistic Analysis of the Power of Arithmetic Filters (1996)
Devillers, Olivier, Preparata, Franco P.
The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...
A Probabilistic Analysis of the Power of Arithmetic Filters (1996)
Devillers, Olivier, Preparata, Franco P.
The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...
Strategic Directions in Computational Geometry (1996)
Roberto Tamassia, Roberto Tamassia (editor, Pankaj K. Agarwal, Nancy Amato, Danny Z. Chen, David Dobkin, ...
ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...
Efficient Approximation Algorithms for Some Semidefinite Programs (1996)
Hsueh-i Lu, N. Klein, Franco P. Preparata, Pascal Van Hentenryck
ization problems. Nonlinear programming did not receive as much attention in this respect until the recent work by Goemans and Williamson [62]. They use semidefinite programs, which are nonlinear...
Robust Proximity Queries in Implicit Voronoi Diagrams (1996)
Giuseppe Liotta, F. P. Preparata, Roberto Tamassia, Franco P. Preparata, Roberto Tamassia
In the context of methodologies intended to confer robustness to geometric algorithms, we elaborate on the exact computation paradigm and formalize the notion of degree of a geometric algorithm, as a...
A Probabilistic Analysis of the Power of Arithmetic Filters (1996)
Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Thème Génie Logiciel, Projet Prisme
The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recentyears, since digital computers do not exhibit such...
Processor-Time Tradeoffs under Bounded-Speed Message Propagation: Part I, Upper Bounds (1995)
Franco Preparata, Gianfranco Bilardi, Gianfranco Bilardi, Franco P. Preparata
Upper bounds are derived for the processor-time tradeoffs of machines such as linear arrays and two-dimensional meshes, which are compatible with the physical limitation expressed by bounded-speed...
Evaluating signs of determinants using single-precision arithmetic (1994)
Avnaim, Francis, Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P., Yvinec, Mariette
We propose a method to evaluate signs of $2\times 2$ and $3\times 3$ determinants with $b$-bit integer entries using only $b$ and $(b+1)$-bit arithmetic respectively. This algorithm has numerous...
Evaluating signs of determinants using single-precision arithmetic (1994)
Avnaim, Francis, Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P., Yvinec, Mariette
We propose a method to evaluate signs of $2\times 2$ and $3\times 3$ determinants with $b$-bit integer entries using only $b$ and $(b+1)$-bit arithmetic respectively. This algorithm has numerous...
Evaluating signs of determinants using single-precision arithmetic (1994)
Avnaim, Francis, Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P., Yvinec, Mariette
We propose a method to evaluate signs of $2\times 2$ and $3\times 3$ determinants with $b$-bit integer entries using only $b$ and $(b+1)$-bit arithmetic respectively. This algorithm has numerous...
A Practical Constructive Scheme for Deterministic Shared-Memory Access (1993)
Franco P. Preparata, Andrea Pietracaprina, Andrea Pietracaprina
CONTACT AUTHOR:
Steiner Trees and Beyond: Approximation Algorithms for Network Design (1993)
Ramamurthy Ravi, Ramamurthy Ravi, Philip N. Klein, Paris C. Kanellakis, Franco P. Preparata
We present approximation algorithms for several NP-hard optimization problems arising in network design. Almost all of our algorithms run in polynomial time and output solutions with a worst-case...
Horizons of Parallel Computation (1993)
Gianfranco Bilardi, Gianfranco Bilardi, Franco P. Preparata, Franco P. Preparata
This paper considers the ultimate impact of fundamental physical limitations---notably, speed of light and device size---on parallel computing machines. Although we fully expect an innovative and...
A Unified Approach To Dynamic Point Location, Ray Shooting, And Shortest Paths In Planar Maps (1993)
Yi-Jen Chiang, Franco P. Preparata, Roberto Tamassia
. We describe a new technique for dynamically maintaining the trapezoidal decomposition of a connected planar map M with n vertices, and apply it to the development of a unified dynamic data...
A Time-Optimal Parallel Algorithm for 3D Convex Hulls (1993)
Nancy M. Amato, Franco P. Preparata
In this paper we present an O( 1 ff log n) time parallel algorithm for computing the convex hull of n points in ! 3 . This algorithm uses O(n 1+ff ) processors on a CREW PRAM, for any constant 0 ! ff...
A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps (1993)
Yi-Jen Chiang, Franco P. Preparata, Roberto Tamassia
. We describe a new technique for dynamically maintaining the trapezoidal decomposition of a connected planar map M with n vertices, and apply it to the development of a unified dynamic data...
Motion planning of legged robots : the spider robot problem (1992)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P., Donati, L.
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can...
Motion planning of legged robots : the spider robot problem (1992)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P., Donati, Leonbattista
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can...
Motion planning of legged robots : the spider robot problem (1992)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P., Donati, Leonbattista
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can...
Fault-Tolerant and Efficient Parallel Computation (1992)
Alexander Allister Shvartsman, Alexander Allister Shvartsman, Alexander Allister, Paris C. Kanellakis, Franco P. Preparata, Jeffrey S. Vitter
ii c fl Copyright 1992 by
A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps (1992)
Yi-jen Chiang, Yi-jen Chiang, Franco P. Preparata, Franco P. Preparata, Roberto Tamassia
We describe a new technique for dynamically maintaining the trapezoidal decomposition of a planar map M with n vertices, and apply it to the development of a unified dynamic data structure that...
Motion Planning of Legged Robots: The Spider Robot Problem (1992)
E De Recherche, Route Des Lucioles, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Olivier Devillers, Olivier Devillers, ...
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can...
Computing the union of 3-colored triangles (1991)
Jean-daniel Boissonnat, Olivier Devillers, Franco P. Preparata
Given is a set S of n points, each colored with one of k 3 colours. We say that a triangle defined by three points of S is 3-colored if its vertices have distinct colours. We prove in this paper that...
Computing The Union Of 3-Colored Triangles (1991)
Jean-daniel Boissonnat, Olivier Devillers, Franco P. Preparata
Given is a set S of n points, each colored with one of k 3 colours. We say that a triangle defined by three points of S is 3-colored if its vertices have distinct colours. We prove in this paper that...
Computing the union of 3-colored triangles (1990)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P.
Computing the union of 3-colored triangles (1990)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P.
Disponible dans les fichiers attachés à ce document
Computing the union of 3-colored triangles (1990)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P.
Disponible dans les fichiers attachés à ce document
Bilardi, Gianfranco, Preparata, Franco P.
The prefix problem consists of computing all the products $x_{0}x_{1} \ldots x_{j} (j = 0, \ldots,N - 1)$, given a sequence $x =(x_{0},x_{1},\ldots, x_{N-1})$ of elements in a semigroup. It is shown...
Bilardi, Gianfranco, Preparata, Franco P.
The prefix problem consists of computing all the products $x_{0}x_{1} \ldots x_{j} (j = 0, \ldots,N - 1)$, given a sequence $x =(x_{0},x_{1},\ldots, x_{N-1})$ of elements in a semigroup. It is shown...
On the boundary of a union of rays (1988)
Alevizos, Panagiotis, Boissonnat, Jean-Daniel, Preparata, Franco P.
Disponible dans les fichiers attachés à ce document
On the boundary of a union of rays (1988)
Alevizos, Panagiotis, Boissonnat, Jean-Daniel, Preparata, Franco P.
Disponible dans les fichiers attachés à ce document
Size-Time Complexity of Boolean Networks for Prefix Computations (1987)
Bilardi, Gianfranco, Preparata, Franco P.
The prefix problem consists of computing all the products $x_{0}x_{1}\ldots x_{j} (j=0,\ldots,N-1)$, given a sequence $X = (x_{0},x_{1},\ldots,x_{N-1})$ of elements in a semigroup. In this paper we...
Size-Time Complexity of Boolean Networks for Prefix Computations (1987)
Bilardi, Gianfranco, Preparata, Franco P.
The prefix problem consists of computing all the products $x_{0}x_{1}\ldots x_{j} (j=0,\ldots,N-1)$, given a sequence $X = (x_{0},x_{1},\ldots,x_{N-1})$ of elements in a semigroup. In this paper we...
Parallel and distributed computingresearch annual / editor Franco P. Preparata (1987)
Incluye bibliografía e índice
On the external boundary of a union of rays* (1987)
Boissonnat, Jean-Daniel, Preparata, Franco P.
Disponible dans les fichiers attachés à ce document
On the external boundary of a union of rays* (1987)
Boissonnat, Jean-Daniel, Preparata, Franco P.
Disponible dans les fichiers attachés à ce document
Area-Time Optimal Division for $T=\Omega((\log n)^1+\epsilon)$ (1987)
Mehlhorn, Kurt, Preparata, Franco P.
Area-time optimal VLSI division circuits are described for all computation times in the range for arbitrary > 0.
Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones (1987)
Alt, Helmut, Hagerup, Torben, Mehlhorn, Kurt, Preparata, Franco P.
The authors describe a nonuniform deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number $n$...
Deterministic Simulation of Idealized Parallel Computers on more Realistic Ones (1987)
Alt, Helmut, Hagerup, Torben, Mehlhorn, Kurt, Preparata, Franco P., Albrecht, Andreas, Jung, Hermann, ...
Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones (1986)
Alt, Helmut, Hagerup, Torben, Mehlhorn, Kurt, Preparata, Franco P., Gruska, Jozef, Rovan, Branislav, ...
Area-time Optimal Division for T=Omega(log n)$^1+epsilon$" (1986)
Mehlhorn, Kurt, Preparata, Franco P., Monien, Burkhard, Vidal-Naquet, Guy
Deterministic simulation of idealized parallel computers on more realistic ones (1985)
Alt, Helmut, Hagerup, Torben, Mehlhorn, Kurt, Preparata, Franco P.
VlSI theory : a research annual / editor Franco P. Preparata (1984)
Incluye bibliografía e índice
Computational geometry : a research annual / editor Franco P. Preparata (1983)
Incluye bibliografía e índice
Aera-time optimal VLSI circuits for convolution (1980)
Baudet, G., Preparata, Franco P., Vuillemin, J.
résumé
Area-time optimal VLSI networks based on the cube-connected-cycles (1980)
Preparata, Franco P., Vuillemin, J.
summary
Aera-time optimal VLSI circuits for convolution (1980)
Baudet, G., Preparata, Franco P., Vuillemin, J.
résumé
Area-time optimal VLSI networks based on the cube-connected-cycles (1980)
Preparata, Franco P., Vuillemin, J.
summary
Preparata, Franco P, Yeh, Raymond T
Incluye índice
Robust Proximity Queries: an Illustration of Degree-driven Algorithm Design
Giuseppe Liotta, Franco P. Preparata, Roberto Tamassia
In the context of methodologies intended to confer robustness to geometric algorithms, we elaborate on the exact computation paradigm and formalize the notion of degree of a geometric algorithm, as a...