Arrow Research search

Author name cluster

F.P. Preparata

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers
1 author row

Possible papers

7

I&C Journal 1988 Journal Article

Minimum polygonal separation

  • H. Edelsbrunner
  • F.P. Preparata

In this paper we study the problem of polygonal separation in the plane, i. e. , finding a convex polygon with minimum number k of sides separating two given finite point sets (k-separator), if it exists. We show that for k = Θ(n), Ω(n log n) is a lower bound to the running time of any algorithm for this problem, and exhibit two algorithms of distinctly different flavors. The first relies on an O(n log n)-time preprocessing task, which constructs the convex hull of the internal set and a nested star-shaped polygon determined by the external set; the k-separator is contained in the annulus between the boundaries of these two polygons and is constructed in additional linear time. The second algorithm adapts the prune-and-search approach, and constructs, in each iteration, one side of the separator; its running time is O(kn), but the separator may have one more side than the minimum.

Details DOI

TCS Journal 1983 Journal Article

Optimal off-line detection of repetitions in a string

  • A. Apostolico
  • F.P. Preparata

An algorithm is presented to detect—within optimal time O(n log n) and space O(n), off-line on a RAM—all of the distinct repetitions in a given textstring on a finite alphabet. The proposed strategy is self-contained, as it depends more heavily on algorithmic design considerations than on the combinatorial properties of the output. It is based on a new data structure, the leaf-tree, which is particularly suited to exploit simple properties of the suffix tree associated with the string to be analyzed.

Details DOI

TCS Journal 1979 Journal Article

Finding the intersection of n half-spaces in time O(n log n)

  • F.P. Preparata
  • D.E. Muller

Given a set of n half-spaces in three dimensional space, we develop an algorithm for finding their common intersection in time O(n log n). The intersection, if nonempty, is presented as a convex polyhedron. The algorithm is summarized as follows: (i) the half-spaces are placed in two sets depending upon whether they contain or do not contain the origin; (ii) the half-spaces in each of these sets are dualized to points, and the convex hulls of the dualized sets are obtained in time O(n log n); (iii) since the half-space intersection is nonempty if and only if these two convex hulls are disjoint, a separating plane is found, also in time O(n log n); (iv) after applying a linear spatial transformation which maps the separating plane to infinity, the convex hull of the union of the two transformed convex hulls is the transformed intersection of the half-spaces. Since the letter can be found in time O(n), the overall running time of the procedure is O(n log n). A significant consequence of this result is that a three-variable linear, or convex, programming problem can be asymptotically solved faster than by the Simplex algorithm, in the worst case.

Details DOI

TCS Journal 1978 Journal Article

Finding the intersection of two convex polyhedra

  • D.E. Muller
  • F.P. Preparata

Given two convex polyhedra in three-dimensional space, we develop an algorithm to (i) test whether their intersection is empty, and (ii) if so to find a separating plane, while (iii) if not to find a point in the intersection and explicitly construct their intersection polyhedron. The algorithm runs in timeO (n log n), where n is the sum of the numbers of vertices of the two polyhedra. The part of the algorithm concerned with (iii) (constructing the intersection) is based upon the fact that if a point in the intersection is known, then the entire intersection is obtained from the convex hull of suitable geometric duals of the two polyhedra taken with respect to this point.

Details DOI

TCS Journal 1978 Journal Article

The densest hemisphere problem

  • D.S. Johnson
  • F.P. Preparata

Given a set K of n points on the unit sphere S d in d-dimensional Euclidean space, a hemisphere of Sd is densest if it contains a largest subset of K. In this paper we consider the problem of determining a densest hemisphere and present the following complementary results: (i) a discretized version of the original problem, restated as a feasibility question, is NP-complete when both n and d are arbitrary; (ii) when the number d of dimensions is fixed, there exists a polynomial time algorithm which solves the problem in time O(n d−1 log n) on a random access machine with unit cost arithmetic operations.

Details DOI

TCS Journal 1975 Journal Article

A fast stable sorting algorithm with absolutely minimum storage

  • F.P. Preparata

An algorithm is described which sorts n numbers in place with the property of stability, i. e. , preserving the original order of equal elements. The algorithm requires absolutely minimum storage 0 (log2 n) bits for program variables and a computation time at most 0 (n (log2 n)2).

Details DOI
v2026.09.13