We introduce the unoriented $\Theta$-maximum as a new criterion for describing the shape of a set of planar points. We present efficient algorithms for computing the unoriented $\Theta$-maximum of a set of planar points. We also propose a simple linear expected time algorithm for computing the unoriented $\Theta$-maximum of a set of planar points when $\Theta=\pi/2$.

No abstract available.

No abstract available.

A convex polytope is the bounded intersection of finite set H of halfspaces. A classic theorem of convexity theory is that every convex polyhedron can be expressed as the convex hull of its set V of vertices. There are three closely related computational problems related to the two descriptions of a polytope. The vertex enumeration problem is to compute V from H. The convex hull problem it to compute H from V. The polytope verification problem is to decide whether a given vertex description and halfspace description define the same polytope. The first two problems are essentially equivalent under point/hyperplane duality. It is an open problem whether any of these problems can be solved in time polynomial in jHj + jVj. In this paper we describe hard polytopes for convex hull algorithms based on pivoting , those based on triangulation, and for some insertion algorithms. 1 Introduction Although the simplex method had long been regarded as a practical and efficient algorithm for linear...

We present a new pivot-based algorithm which can be used with minor modification for the enumeration of the facets of the convex hull of a set of points, or for the enumeration of the vertices of an arrartgement or of a convex polyhedron, in arbitrary dimension.The algorithm has the following properties: (a) No additional storage is required beyond the input dam, (b) The output list produced is frw of duplicates; (c) The algorithm is extremely simple, requires no data structures, and handles all degenerate cases; (d) The running time is output sensitive for nondegenerate inputs; (e) The algorithm is easy to efficiently paraIIeIize.For example, the algorithm finds the v vertices of a polyhedron in R d defined by a non-degenerate system of n inequalities (or dually, the v facets of the convex hull of n points in R ~, where each facet contains exactly d given points) in time O (ndv ) and O (rid) space.The v vertices in a simple arrangement of n hyperplanes in R d can be found in O (n2dv ) time and O (rid) space complexity.The algorithm is based on inverting finite pivot algorithms for linear programming.

Abstract A finite metric (or more properly semimetric) on n points is a nonnegative vector d = (dij) 1 ⩽ i < j ⩽ n that satisfies the triangle inequality dij ⩽ dik + djk. The L1 (or Manhattan) distance ‖x − y‖1 between two vectors x = (xi) and y = (yi) in Rm is given by ‖x − y‖1 = ∑1⩽i⩽m |xi − yi|. A metric d is L1‐embeddable if there exist vectors z1, z2,…, zn in Rm for some m, such that dij = ‖zi − zj‖1 for 1 ⩽ i < j ⩽ n. A cut metric is a metric with all distances zero or one and corresponds to the incidence vector of a cut in the complete graph on n vertices. The cut cone Hn is the convex cone formed by taking all nonnegative combinations of cut metrics. It is easily shown that a metric is L1‐embeddable if and only if it is contained in the cut cone. In this expository paper, we provide a unified setting for describing a number of results related to L1‐embeddability and the cut cone. We collect and describe results on the facial structure of the cut cone and the complexity of testing the L1‐embeddability of a metric. One of the main sections of the paper describes the role of L1‐embeddability in the feasibility problem for multi‐commodity flows. The Ford and Fulkerson theorem for the existence of a single commodity flow can be restated as an inequality that must be valid for all cut metrics. A more general result, known as the Japanese theorem, gives a condition for the existence of a multicommodity flow. This theorem gives an inequality that must be satisfied by all metrics. For multicommodity flows involving a small number of terminals, it is known that the condition of the Japanese theorem can be replaced with one of the Ford–Fulkerson type. We review these results and show that the existence of such Ford–Fulkerson‐type conditions for flows with few terminals depends critically on the fact that certain metrics are L1‐embeddable.

The complexity of the single-fault (SF) set diagnosability and SF-diagnosis problems under the symmetric invalidation models is discussed. It is shown that the SF-diagnosis problem under both these models is co-NP-complete and the SF-diagnosability problem is also co-NP-complete under the asymmetric invalidation model. The SF-diagnosability problem is also studied under the symmetric-invalidation model and a polynomial time-complexity algorithm is presented. These results are in contrast with the corresponding t-diagnosability and t-diagnosis problems, which are known to have polynomial time-complexity algorithms.>

We present a heuristic to solve the $m \times m$ assignment problem in $O(m^2 )$ time. The assignment problem is formulated as a weighted complete bipartite graph $G = (S,T,E)$, $|S| = |T| = m$. For convenience we assume that m is even. The main procedure in the heuristic is to construct a graph $G_d = (S,T,E_d )$ which is a subgraph of G, $|E_d | = 4dn$, $n = {m / 2}$, such that we can find a perfect matching in $G_d $ with probability at least $1 - \frac{1}{3}({d / n})^{d^2 - 4d - 1} $. An $O(|S||E|)$ exact algorithm is used to find a minimum weight matching M in $G_d $. Any unmatched vertices in G relative to M are then matched by a greedy algorithm. The expected value of the total cost of the matching found by the heuristic is shown to be less than six if the costs are independent and identically distributed uniformly in the unit interval. Further, with the above probability, the heuristic produces a solution which is at most six times the optimal solution.

Algorithms are developed for determining if a set of polyhedral objects in R3 can be intersected by a common transversal (stabbing) line. It can be determined in Ο(n) time if a set of n lines in space has a line transversal, and such a transversal can be found in the same time bound. For a set of n line segments, the complexity of finding such a transversal becomes Ο(nlogn). Finally, for a set of polyhedra with a total of n vertices, we give a Ο(n5) algorithm for determining the existence of, and computing, a line transversal. Helly-type theorems for lines and segments are also given. In particular, it is shown that if every six of a set of lines in space are intersected by a common transversal, then the entire set has a common transversal.

System-level diagnosis appears to be a viable alternative to circuit-level testing in complex multiprocessor systems. A completely new generalization of the characterization problem in the system-level diagnosis area is developed in this paper. This generalized characterization theorem provides necessary and sufficient conditions for any fault-pattern of any size to be uniquely diagnosable, under the symmetric, and asymmetric invalidation models with or without the intermittent faults. Moreover, it is also shown that the well known t-characterization theorems under these models can be derived as special cases. In addition to the generalization provided by these results, it is hoped that these results will also have a great impact on the diagnosis of faulty units in uniform structures based on the system-level diagnosis concepts and would be particularly useful in the diagnosis of WSI-oriented multiprocessor systems.

A set P of points in Rd is called simplicial if it has dimension d and contains exactly d + 1 extreme points. We show that when P contains n interior points, there is always one point, called a splitter, that partitions P into d + 1 simplices, none of which contain more than dn /(d + 1) points. A splitter can be found in O (d4n) time. Using this result, we give a O (d4n log1+1/dn) algorithm for triangulating simplicial point sets that are in general position. In R3 we give an O (n logn + k) algorithm for triangulating arbitrary point sets, where k is the number of simplices produced. We exhibit sets of 2n + 1 points in R3 for which the number of simplices produced may vary between (n -1)2 + 1 and 2n -2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.

We consider the problem of partitioning sets of n points in d dimensions by means of κ intersecting hyperplanes. We collect known results on this problem and give some new results. In particular, for d=κ=3 it is known that a set in general position can be split into equal parts given any initial bisecting plane and two other carefully chosen planes. We show that this result does not extend to the case d=κ=4. We also give bounds on the smallest integer h(κ) such that sets in h(κ)-space can be partitioned by κ hyperplanes into 2κ subsets of equal cardinality, partially answering a question raised by Paul Erdös.

A largest empty convex subset of a finite set of points, S, is a maximum cardinality subset of S, that (1) are the vertices of a convex polygon, and (2) contain no other points of S interior to their convex hull. An Ο(n3) time and Ο(n2) space algorithm is introduced to find such subsets, where n represents the cardinality of S. Empirical results are obtained and presented. In particular, a configuration of 20 points is obtained with no empty convex hexagon, giving a partial answer to a question of Paul Erdös.

Abstract This survey paper reviews results on heuristics for two weighted matching problems: matchings where the vertices are points in the plane and weights are Euclidean distances, and the assignment problem. Several heuristics are described in detail and results are given for worst‐case ratio bounds, absolute bounds, and expected bounds. Applications to practical problems and some mathematical complements are also included.

A new approach is presented to the classification problem of planar shapes represented by polygons. A shape is abstracted combinatorially by means of its visibility graph, and two shapes are deemed similar whenever their graphs are cyclically isomorphic. Efficient algorithms are presented for performing these operations.

In many computer applications areas such as graphics, automated cartography, image processing, and robotics the notion of visibility among objects modeled as polygons is a recurring theme. This paper is concerned with the visibility of a simple polygon from one of its edges. Three natural definitions of the visibility of a polygon from an edge are presented. The following computational problem is considered. Given an n-sided simple polygon, is the polygon visible from a specified edge? An O(n), and thus optimal, algorithm is exhibited for determining edge visibility under any of the three definitions. The paper closes with an interesting characterization of visibility and some open problems in this area.

Let P be a polyhedron with fs s-dimensional faces. We show that Ω(log fs) linear comparisons are needed to determine if a point lies in P. This is used to establish an Ω(n2 log n) lower bound to the all-pairs shortest path problem between n points.