Franco P. Preparata

TCS Journal 2008 Journal Article

The unpredictable deviousness of models

• Franco P. Preparata

Computation models are central to algorithmic research. A model, designed to capture the essential features of a technology dispensing with irrelevant and burdensome details, is a judicious compromise between simplicity and fidelity (or reflectivity). This approach has unleashed an enormous amount of valuable algorithmic research over the years. However, the pursuit of simplicity may filter out details, once deemed irrelevant, which may later reassert their significance under either technological pressure or more careful scrutiny, in which case the inadequacy of the model cripples the validity of the derived results. Examples of this situation, drawn from computational geometry, numerical parallel computation, VLSI theory, and computational biology, will be reviewed and examined in detail.

TCS Journal 2001 Journal Article

Generalized scans and tridiagonal systems

• Paul F. Fischer
• Franco P. Preparata
• John E. Savage

Motivated by the analysis of known parallel techniques for the solution of linear tridiagonal system, we introduce generalized scans, a class of recursively defined length-preserving, sequence-to-sequence transformations that generalize the well-known prefix computations (scans). Generalized scan functions are described in terms of three algorithmic phases, the reduction phase that saves data for the third or expansion phase and prepares data for the second phase which is a recursive invocation of the same function on one fewer variable. Both the reduction and expansion phases operate on bounded number of variables, a key feature for their parallelization. Generalized scans enjoy a property, called here protoassociativity, that gives rise to ordinary associativity when generalized scans are specialized to ordinary scans. We show that the solution of positive-definite block tridiagonal linear systems can be cast as a generalized scan, thereby shedding light on the underlying structure enabling known parallelization schemes for this problem. We also describe a variety of parallel algorithms including some that are well known for tridiagonal systems and some that are much better suited to distributed computation.

SODA Conference 2000 Conference Paper

Evaluating the cylindricity of a nominally cylindrical point set

• Olivier Devillers
• Franco P. Preparata

SODA Conference 1993 Conference Paper

A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps

• Yi-Jen Chiang
• Franco P. Preparata
• Roberto Tamassia

ICRA Conference 1992 Conference Paper

Motion planning for spider robots

• Jean-Daniel Boissonnat
• Olivier Devillers
• LeonBattista Donati
• Franco P. Preparata

The authors consider a simple instance of the problem of planning motions of legged robots. The robot is modeled as a point where all its legs are attached, and the footholds where the robot can securely place its feet consist of a set of points in the plane. Efficient algorithms to compute stable motions in such situations are presented. >

I&C Journal 1991 Journal Article

Deterministic P-RAM simulation with constant redundancy

• Scot W. Hornick
• Franco P. Preparata

In this paper, we show that distributing the memory of a parallel computer and, thereby, decreasing its granularity allows a reduction in the redundancy required to achieve polylog simulation time for each P-RAM step. Previously, realistic models of parallel computation assigned one memory module to each processor and, as a result, insisted on relatively coarse-grain memory. We propose, on the other hand, a more flexible, but equally valid model of computation, the distributed-memory, bounded-degree network (DMBDN) model. This model allows the use of fine-grain memory while maintaining the realism of a bounded-degree interconnection network. We describe a P-RAM simulation scheme, which is admitted under the DMBDN model, that exploits the increased memory bandwidth provided by a two-dimensional mesh of trees (2DMOT) network to achieve an overhead in memory redundancy lower than that required by other fast, deterministic P-RAM simulations. Specifically, for a deterministic simulation of an n-processor P-RAM on a bounded-degree network, we are able to reduce the number of copies of each variable from O( log n log log n ) to Θ(1) and still simulate each P-RAM step in polylog time.

TCS Journal 1990 Journal Article

Dynamic planar point location with optimal query time

• Franco P. Preparata
• Roberto Tamassia

We present a new dynamic technique for locating a point in a convex planar subdivision whose n vertices lie on a fixed set of N horizontal lines. The supported update operations are insertion/deletion of vertices and edges, and (horizontal) translation of vertices. Our method achieves query time On + log IV, space O(N+n log N). and insertion/deletion time O(log n log N). Hence, for N=O(n), the query time is O(log n), which is optimal. The proposed technique, based on the trapezoid method, provides an efficient solution to many significant applications where the most frequent operation is the point location query, while updates are more rarely executed.

FOCS Conference 1988 Conference Paper

Fully Dynamic Techniques for Point Location and Transitive Closure in Planar Structures (Extended Abstract)

• Franco P. Preparata
• Roberto Tamassia

It is shown that a planar st-graph G admits two total orders on the set V union E union F, where V, E, and F are, respectively, the sets of vertices, edges and faces of G, with mod V mod =n. An O(n) space data structure for the maintenance of the two orders is exhibited that supports an update of G (insertion of an edge and expansion of a vertex, and their inverses) in time O(log n). This data structure also supports transitive-closure queries in O(log n). Moreover, planar st-graphs provide the topological underpinning of a fully dynamic planar point location technique in monotone subdivisions, which is an interesting (unique) specialization of the chain method of Lee-Preparata (1977). While maintaining storage O(n) and query time O(log/sup 2/ n), insertion/deletion of a chain with k edges can be done in time O(log/sup 2/ n+k), and insertion/deletion of a vertex on an edge can be done in time O(log n). >

STOC Conference 1987 Conference Paper

Size-Time Complexity of Boolean Networks for Prefix Computations

• Gianfranco Bilardi
• Franco P. Preparata

The prefix problem consists of computing all the products x 0 x 1 … x j ( j =0, …, N - 1), given a sequence x = ( x 0 , x 1 , …, x N - 1 ) of elements in a semigroup. In this paper we completely characterize the size-time complexity of computing prefixes with boolean networks , which are synchronized interconnections of Boolean gates and one-bit storage devices. This complexity crucially depends upon a property of the underlying semigroup, which we call cycle-freedom (no cycle of length greater than one in the Cayley graph of the semigroup). Denoting by S and T size and computation time, respectively, we have S = Θ(( N/T ) log( N/T )), for non-cycle-free semigroups, and S = Θ( N/T ), for cycle-free semigroups. In both cases, T ∈ [Ω(log N ), O ( N )].

MFCS Conference 1986 Conference Paper

Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones

• Helmut Alt
• Torben Hagerup
• Kurt Mehlhorn
• Franco P. Preparata

Abstract We describe a deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number n of processors as the simulated PRAM, and if the size of the PRAM's shared memory is polynomial in n, each PRAM step is simulated by O (log n ) MPC steps or by O ((log n ) 2 ) steps of the bounded degree network. This improves upon a previous result by Upfal and Wigderson. We also prove an Ω((log n ) 2 /log log n ) lower bound on the number of steps needed to simulate one PRAM step on a bounded degree network under the assumption that the communication in the network is point-to-point.

STOC Conference 1984 Conference Paper

A Minimum Area VLSI Network for O(log n) Time Sorting

• Gianfranco Bilardi
• Franco P. Preparata

MFCS Conference 1984 Invited Paper

VLSI Algorithms and Architectures

• Franco P. Preparata

Abstract In this paper we consider the relationship between algorithms and parallel VLSI architectures. Starting from the premise that VLSI is the natural habitat for parallel algorithmics, we outline the desirable features of VLSI architectures. Next we discuss the notion of algorithmic paradigm, as the data transfer pattern of a class of specific algorithms. The recursive combination paradigm (applicable to merging, sorting, FFT, permutation, etc.), is naturally mapped to the awkward binary cube architecture. Thus we analyze four viable architectures — the shuffle-exchange, the linear array, the mesh, and the cube-connected-cycles — which emulate the binary cube. Finally, we illustrate the mechanisms of pipelining, pleating, and mixing, which play a significant role in matching algorithms and architectures.

FOCS Conference 1982 Conference Paper

Three Layers Are Enough

• Franco P. Preparata
• Witold Lipski Jr.

In this paper we show that any channel routing problem of density d involving two-terminal nets can always be solved in the knock-knee mode in a channel of width equal the density d with three conducting layers. An algorithm is described which produces a layout of n nets with the following properties: (i) it has minimal width d; (ii) it can be realized with three layers; (iii) it has at most 3n vias; (iv) any two wires share at most four grid points.

FOCS Conference 1979 Conference Paper

The Cube-Connected-Cycles: A Versatile Network for Parallel Computation (Extended Abstract)

• Franco P. Preparata
• Jean Vuillemin

We introduce a network of processing elements, the cube-connected-cycles (CCC), complying with the present technological constraints of VLSI design. By combining the principles of parallelism and pipelining, the CCC can emulate the cube-connected machine with no significant degradation of performance but with a much more compact structure. We describe in detail how to program the CCC for efficiently solving a large class of problems, which includes Fast-Fourier-Transform, sorting, permutations, and derived algorithms. The CCC can also be used as a general purpose parallel processor.

MFCS Conference 1977 Conference Paper

The Medial Axis of a Simple Polygon

• Franco P. Preparata

STOC Conference 1976 Conference Paper

Location of a Point in a Planar Subdivision and its Applications

• D. T. Lee
• Franco P. Preparata