Search

A rank-one algorithm is presented for unconstrained function minimization. The algorithm is a modified version of Davidon's variance algorithm and incorporates a limited line search. It is shown that the algorithm is a descent algorithm; for quadratic forms, it exhibits finite convergence, in certain cases. Numerical studies indicate that it is considerably superior to both the Davidon-Fletcher-Powell algorithm and the conjugate-gradient algorithm.

A new algorithm is given for finding the convex hull of a finite set of distinct points in three-dimensional space. The algorithm finds the faces of the hull one by one, thus gradually building the polyhedron that constitutes the hull. The algorithm is described as developed through stepwise refinement.

Rewriting and comparisons are the complexity aspects of the unification algorithm which are considered in this paper. A simplified version of Robinson's algorithm [2] is described where rewriting (already linear in the size of the input in [2]) is reduced by a constant factor and the number of comparisons (exponential in the size of the input in [2]) is bounded by a quantity polynomial of quadratic order in the size of the input.

An implementation of an algorithm for computing the convex hull of a finite planar set of points is presented. The program is compared with an algorithm for the same purpose coded previously. Experimental results indicate that our program is superior to the other in terms of both running time and storage requirements.

A parallel algorithm is presented for computing the convex hull of a set ofn points in the plane. The algorithm usesn1−e processors, 0

A method is presented for determining the three-dimensional convex hull of a real object that is approximated in computer storage by a polyhedron. Essentially, this technique tests all point pairs of the polyhedron for convex edges of the convex hull and then assembles the edges into the polygonal boundaries of each of the faces of the convex hull. Various techniques for optimizing this process are discussed. A computer program has been written, and typical output shapes are illustrated. Finding the three-dimensional convex hull is approximately the same computer burden as eliminating hidden lines.

We study the cutting plane algorithm for convex non-smooth programming and deduce a cutting plane algorithm for (convex) fractional programming. The resultart algorithm is a simpler version of an algorithm due to Crouzeix-Ferland- Schaible.

We present a new planar convex hull algorithm with worst case time complexity $O(n \log H)$ where $n$ is the size of the input set and $H$ is the size of the output set, i.e. the number of vertices found to be on the hull. We also show that this algorithm is asymptotically worst case optimal on a rather realistic model of computation even if the complexity of the problem is measured in terms of input as well as output size. The algorithm relies on a variation of the divide-and-conquer paradigm which we call the ``marriage-before-conquest'''' principle and which appears to be interesting in its own right.

This paper presents a new descent algorithm for minimizing a convex function which is not necessarily differentiable. The algorithm can be implemented and may be considered a modification of the e-subgradient algorithm and Lemarechal's descent algorithm. Also our algorithm is seen to be closely related to the proximal point algorithm applied to convex minimization problems. A convergence theorem for the algorithm is established under the assumption that the objective function is bounded from below. Limited computational experience with the algorithm is also reported.

The problem of construction of planar Voronoi diagrams arises in many areas, one of the most important of which is in nearest neighbor problems. This includes clustering [ 141, contour maps [6] and (Euclidean) minimum spanning trees [23]. Shamos [22] gives several more applications. An JZ(N log N) time worst case lower bound can be shown for this problem by reducing it to sorting [2 11. The challenge is to construct an O(N log N) time algorithm. Shamos [213 and Shamos anti Hoey [23] describe an O(N log N) time divide-and-conquer algorithm for construction of the planar Euclidean Voronoi diagram. Lee and Wong [ 161 describe an O(N log N) time algorithm for the L1 and L, metrics in the plane, and Drysdale pnd Lee [8] present an O(N@g N)l/*) t’ rme algorithm for the Voronoi diagram of N line segments (which they have since improved to O(N(log N)*) time). Shamos [2 11, Lee and Preparata [ 151, and Lipton and Tarjan [ 171 have produced fast algorithms for searching a Voronoi diagram (or any other straight-line planar graph). In this paper we describe an O(N log N) time algorithm for constructing a planar Euclidean Voronoi diagram which extends straightforwardly to higher dimensions. The fundamental result is that a K-dimensional Euclidean Voronoi diagram of N points can be constructed by transforming the points to K + I-space

For a large class of time functionsT, we show the following: Assuming that there is some parallel processor which requiresθ(T(j)) time units when searching the minimum amongj arbitrary points with respect to an arbitrary rotational ordering. Then the planar Convex Hull Problem forn points is of the complexityθ(nT(n)).

Two parallel algorithms for determining the convex hull of a set of data points in two dimensional space are presented. Both are suitable for MIMD parallel systems. The first is based on the strategy of divide-and-conquer, in which some simplest convex-hulls are generated first and then the final convex hull of all points is achieved by the processes of merging 2 sub-convex hulls. The second algorithm is by the process of picking up the points that are necessarily in the convex hull and discarding the points that are definitely not in the convex hull. Experimental results on a MIMD parallel system of 4 processors are analysed and presented.

An algorithm to select the minimum-cost collection of binary-valued features for use with a linear pattern classifier is presented. The feature-selection algorithm is motivated by the convex-hull representation of pattern-space separability. Combinatorial analysis and linear programming are used to find the minimum-cost collection of binary-valued features associated with a given set of preclassified patterns. A description of the interaction between these algorithm components is provided. The algorithm guarantees that its optimal feature set will correctly classify every pattern in the classifier's training sample. Coinputational considerations associated with algorithm use are discussed. An application of the algorithm to a three-feature classifier is presented in detail.

We present efficient parallel algorithms for several basic problems in computational geometry: convex hulls, Voronoi diagrams, detecting line segment intersections, triangulating simple polygons, minimizing a circumscribing triangle, and recursive data-structures for three-dimensional queries.

Given two ordered vectors of n elements each, a simple algorithm is proposed to merge them in-place, i.e., using only a fixed amount of extra storage. The combinatorial problems raised by the analysis of the algorithm are solved, showing that its average running time is in the order of O ( n 1.5 ). The algorithm is then extended to vectors of any size. Finally, the “divide and conquer” methodology is applied to reduce the complexity of the algorithm to O ( n 1.2 ).

Kirkpatrick and Seidel [13,14] recently proposed an algorithm for computing the convex hull of n points in the plane that runs in O(n log h) worst case time, where h denotes the number of points on the convex hull of the set. Here a modification of their algorithm is proposed that is believed to run in O(n) expected time for many reasonable distributions of points. The above O(n log h) algorithmsare experimentally compared to the O(n log n) 'throw-away' algorithms of Akl, Devroye and Toussaint [2, 8, 20]. The results suggest that although the O(n Log h) algorithms may be the 'ultimate' ones in theory, they are of little practical value from the point of view of running time.

This paper gives an algorithm to compute the least fixed-point of a system of equations over a transition system. This algorithm has a time complexity linear in the size of the transition system, thus improving the known algorithms which are quadratic.

A two-stage algorithm was recently proposed by Sklansky (1982) for computing the convex hull of a simple polygon P. The first step is intended to compute a simple polygon P^* which is monotonic in both the x and y directions and which contains the convex hull vertices of P. The second step applies a very simple convex hull algorithm on P^*. In this note we show that the first step does not always work correctly and can even yield non-simple polygons, invalidating the use of the second step. It is also shown that the first step can discard convex hull vertices thus invalidating the use of any convex hull algorithm in the second step.

The volume of the convex hull of anym points of ann-dimensional ball with volumeV is at mostV·m/2n. This implies that no polynomial time algorithm can compute the volume of a convex set (given by an oracle) with less than exponential relative error. A lower bound on the complexity of computing width can also be deduced.

This paper is concerned with the nature of speedups. Let f be any recursive func- tion. We show that there is no effective procedure for going from an algorithm forf to another algorithm for f that is significantly faster on all but a finite number of inputs. On the other hand, for a large class of functions f, one can go effectively from any algorithm for f to one that is faster on at least infinitely many integers. Finally, if one has an algorithm for a given function f, and if there is an algorithm which is faster on all but a finite number of inputs, then even though one cannot get this faster algorithm effectively, one can still obtain a pseudo- speedup: This is a very fast algorithm which computes a variant of the function, one which differs from the original function on a finite number of inputs.

The solution of the Chinese postman problem using matching theory is given. The convex hull of integer solutions is described as a linear programming polyhedron. This polyhedron is used to show that a good algorithm gives an optimum solution. The algorithm is a specialization of the more generalb-matching blossom algorithm. Algorithms for finding Euler tours and related problems are also discussed.

An n log n lower bound is found for linear decision tree algorithms with integer inputs that either identify the convex hull of a set of points or compute its cardinality.

Given a convex body C in the plane, its discrete hull is C0 = ConvexHull(C ∩ L), where L = Z × Z is the integer lattice. We present an O(C0logδ(C))-time algorithm for calculating the discrete hull of C, where C0 denotes the number of vertices of C0, and δ(C) is the diameter of C. Actually, using known combinatorial bounds, the running time of the algorithm is O(δ(C) 2 3 logδ(C)) . In particular, this bound applies when C is a disk.

In this paper we give an optimal algorithm for constructing the convex hull of a partially sorted set S of n points in R 2 . Specifically, we assume S is represented as the union of a collection of non-empty subsets S 0 , S 1 , S 2 ,…, S m , where the x -coordinate of each point in S i is smaller than the x -coordinate of any point in S j if i j . Our method runs in O( n log h max ) time, where h max is the maximum number of hull edges incident on the points of any single subset S i . In fact, if one is only interested in finding the hull edges that ‘bridge’ different subsets, then our method runs in O( n ) time.

We describe the first optimal randomized in-place algorithm for the basic 3-d convex hull problem (and, in particular, for 2-d Voronoi diagrams). The algorithm runs in O(nlogn) expected time using only O(1) extra space; this improves the previous O(nlog3n) bound by Brönnimann, Chan, and Chen (2004) [10]. The same approach leads to an optimal randomized in-place algorithm for the 2-d line segment intersection problem, with O(nlogn+K) expected running time for output size K, improving the previous O(nlog2n+K) bound by Vahrenhold (2007) [42]. As a bonus, we also point out a simplification of a known optimal cache-oblivious (non-in-place) algorithm by Kumar and Ramos (2002) [33] for 3-d convex hulls, and observe its applicability to 2-d segment intersection, extending a recent result for red/blue segment intersection by Arge, Mølhave, and Zeh (2008) [3]. Our results are all obtained by standard random sampling techniques, with some interesting twists.

Let S be any family of n c-oriented polygons of the two-dimensional Euclidean plane E2, i.e., bounded intersection of halfplanes whose normal directions of edges belong to a fixed collection of c distinct directions. Let φ(S) denote the packing number of S, that is the maximum number of pairwise disjoint objects of S. Let τ(S) be the transversal number of S, that is the minimum number of points required so that each object contains at least one of those points. We prove that τ(S)⩽G(2,c)φ(S)log2c−1(φ(S)+1), where G(2,c) is the Gallai number of pairwise intersecting c-oriented polygons. Our bound collapses to τ(S)=O(G(2,c)φ(S)) if objects are more or less of the same size. We describe a t(n,c)+O(nclogφ(S))-time algorithm with linear storage that computes such a 0-transversal, where t(n,c) is the time required to pierce pairwise intersecting c-oriented polygons. We provide linear-time algorithms t(n,c)=Θ(nc) for α-fat c-oriented polytopes, translates or homothets of Ed proving that G(2,c)=O(α)d, G(2,c)⩽dd and G(2,c)⩽(3d3/2)d respectively.

The relationship between a three-dimensional convex hull and many important two-dimensional diagrams is surveyed, and a unifying approach to robust software for those diagrams is proposed. In this approach, instead of implementing individual algorithms, we first construct a robust algorithm for the three-dimensional convex hull, and next use it as an oracle for computing the other diagrams. The diagrams computable by this approach include the Voronoi diagram and its farthest-point versions both on the plane and on the sphere, the Laguerre Voronoi diagram and its farthest-point version both on the plane and on the sphere, and the intersection of half-spaces.

We present a fixed-parameter algorithm for the Minimum Convex Partition and the Minimum Weight Convex Partition problem. The algorithm is based on techniques developed for the Minimum Weight Triangulation problem. On a set P of n points the algorithm runs in O(2kk4n3+nlogn) time. The parameter k is the number of points in P lying in the interior of the convex hull of P.

We discuss the implementation of an adaptive algorithm proposed by one of us. The algorithm is a hybrid of the gmres method and Richardson's method. Richardson's method ( RM ) depends on a set of parameters that are computed by minimizing the L 2 norm of a polynomial over the convex hull of eigenvalues. Execution of GMRES yields not only an approximate solution but also the approximate convex hull. RM is used to avoid storing and working with a large number of vectors as GMRES often requires. This method is also advantageous for the solution of large problems. We consider several test problems and compare our algorithm primarily with the conjugate-gradient-squared algorithm, but also with GMRES and to CG (applied to the normal equations). For many (test) problems our algorithm takes roughly 50 percent more work than the conjugate-gradient-squared algorithm, although if the matrix is either preconditioned or indefinite, our algorithm is more efficient. However, our algorithm currently imposes an undesirable burden on the user, who is invited to consider a variety of numerical parameters to manipulate, such as the number of steps of rm , in order to enhance performance: the values we suggest are only empirical.

We consider the computation of the convex hull of a given n-point set in three-dimensional Euclidean space in an output-sensitive manner. Clarkson and Shor proposed an optimal randomized algorithm for this problem, with an expected running time O(n log h), where h denotes the number of points on the surface of the convex hull. In this note we point out that the algorithm can be made deterministic by using recently developed techniques, thus obtaining an optimal deterministic algorithm.

In this paper we have designed a randomized algorithm to generate a random polygon P from a given set S ={ p 1 , p 2 ,. . ., p n } of n points lying on a two dimensional plane. As a preprocessing task, we first compute the convex hull layers from the set S in O ( n 2 ) time by modifying the well known Jarvis march algorithm. Next, we execute our algorithm taking the convex hull layers as input to generate random polygons over given point set. This is a Las-Vegas randomized algorithm with O ( n l ogn ) time which is much improved over the existing one. We also give a procedure to count the total number of different polygons that can be generated by our algorithm. This number help us to calculate the probability of generating a unique polygon in each execution which measure the randomness of our algorithm.

In this note some comments on the paper: D.J. Evans and Shao-wen Mai, Two parallel algorithms for the convex hull problem in a two dimensional space, Parallel Computing 2 (1985) 313–326 are given.

A recently proposed algorithm for computing the convex hull of a grey-level histogram in image segmentation is shown to be inefficient due to the fact that it does not exploit the histogram's structure. It is pointed out that a histogram is a weakly externally visible polygon and thus a very simple linear convex hull algorithm will work for such applications.

This paper discusses the construction of the 3-dimensional convex hull for a set of n points stored on a √n × √n mesh of processors. Lu has shown that this problem can be solved in √n log n time if all points are located on a sphere. Here, we solve, in the same time-complexity, the 3-dimensional convex hull problem for arbitrary point sets. Furthermore, we observe a time/space trade off: if each processor is allocated O(log n) space then √n time is sufficient to determine the 3-dimensional convex hull.

We introduce a new randomized sampling technique, called Polling which has applications to deriving efficient parallel algorithms. As an example of its use in computational geometry, we present an optimal parallel randomized algorithm for intersection of half-spaces in three dimensions. Because of well-known reductions, our methods also yield equally efficient algorithms for fundamental problems like the convex hull in three dimensions, Voronoi diagram of point sites on a plane and Euclidean minimal spanning tree. Our algorithms run in time T = O(logn) for worst-case inputs and uses P = O(n) processors in a CREW PRAM model where n is the input size. They are randomized in the sense that they use a total of only O(log2n) random bits and terminate in the claimed time bound with probability 1 - n-a for any a > 0. They are also optimal in P . T product since the sequential time bound for all these problems is O(nlogn). The best known determistic parallel algorithms for 2-D Voronoi-diagram and 3-D Convex hull run in O(log2n) and O(log2nlog * n) time respectively while using O(n) processors.

In this paper we present an algorithm for hidden surface removal for a class of polyhedral surfaces which have a property that they can be ordered relatively quickly like the terrain maps. A distinguishing feature of this algorithm is that its running time is sensitive to the actual size of the visible image rather than the total number of intersections in the image plane which can be much larger than the visible image. The time complexity of this algorithm is O((k +n)lognloglogn) where n and k are respectively the input and the output sizes. Thus, in a significant number of situations this will be faster than the worst case optimal algorithms which have running time O(n2) irrespective of the output size (where as the output size k is O(n2) only in the worst case). We also present a parallel algorithm based on a similar approach which runs in time O(log4(n+k)) using O((n + k)/log(n+k)) processors in a CREW PRAM model. All our bounds are obtained using ammortized analysis.

An algorithm for solving linear programming problems is given. The expected number of arithmetic operations required by the algorithm is given. The expectation is with respect to the random choices made by the algorithm, and the bound holds for any given input. The technique can be extended to other convex programming problems. >

Random sampling is used for several new geometric algorithms. The algorithms are “Las Vegas,” and their expected bounds are with respect to the random behavior of the algorithms. One algorithm reports all the intersecting pairs of a set of line segments in the plane, and requires O(A + n log n) expected time, where A is the size of the answer, the number of intersecting pairs reported. The algorithm requires O(n) space in the worst case. Another algorithm computes the convex hull of a point set in E3 in O(n log A) expected time, where n is the number of points and A is the number of points on the surface of the hull. A simple Las Vegas algorithm triangulates simple polygons in O(n log log n) expected time. Algorithms for half-space range reporting are also given. In addition, this paper gives asymptotically tight bounds for a combinatorial quantity of interest in discrete and computational geometry, related to halfspace partitions of point sets.

This paper contains a description an algorithm for computing four dimensional convex hulls of point sets using the divide-and-conquer paradigm. The algorithm features minimal asymptotic time and memory complexity with respect to the size of its input point set. It is based upon a fully-dual four-dimensional boundary representation (BREP) data structure called Hexblock, also developed by the author, which was inspired by Guibas' and Stolfi's quadedge data structure.

Let $$S \subseteq \mathbb{R}^n $$ be a convex set for which there is an oracle with the following property. Given any pointz∈ℝ n the oracle returns a “Yes” ifz∈S; whereas ifz∉S then the oracle returns a “No” together with a hyperplane that separatesz fromS. The feasibility problem is the problem of finding a point inS; the convex optimization problem is the problem of minimizing a convex function overS. We present a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope are central to the algorithm. Our algorithm has a significantly better global convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts to the convex optimization problem.

The multistage or staircase structure appears naturally in many models with time horizons. This paper presents and discusses a decomposition algorithm when the problem functions are convex. The Dantzig-Wolfe convex programming algorithm is presented as one of the techniques available for solving the generated subproblems. Computational implementation of the algorithm and more efficient techniques in the presence of special structure are discussed.

The k-means algorithm is a frequently used algorithm for solving clustering problems. This algorithm has the disadvantage that it depends on the initial conditions, for that reason, the global k-means algorithm was proposed to solve this problem. On the other hand, the k-means algorithm only works with numerical features. This problem is solved by the k-means algorithm with similarity functions that allows working with qualitative and quantitative variables and missing data (mixed and incomplete data). However, this algorithm still depends on the initial conditions. Therefore, in this paper an algorithm to solve the dependency on initial conditions of the k-means algorithm with similarity functions is proposed, our algorithm is tested and compared against k-means algorithm with similarity functions.

In the calculating of convex hulls for point sets, a preprocessing procedure that is to filter the input points by discarding non-extreme points is commonly used to improve the computational efficiency. We previously proposed a quite straightforward preprocessing approach for accelerating 2D convex hull computation on the GPU. In this paper, we extend that algorithm to being used in 3D cases. The basic ideas behind these two preprocessing algorithms are similar: first, several groups of extreme points are found according to the original set of input points and several rotated versions of the input set; then, a convex polyhedron is created using the found extreme points; and finally those interior points locating inside the formed convex polyhedron are discarded. Experimental results show that: when employing the proposed preprocessing algorithm, it achieves the speedups of about 4x on average and 5x to 6x in the best cases over the cases where the proposed approach is not used. In addition, more than 95 percent of the input points can be discarded in most experimental tests.

We present fast algorithms for penetration detection and contact determination between polyhedral models in dynamic environments. They are based on a distance computation algorithm for convex polytopes and a hierarchical coherence-based algorithm to compute contacts. In particular, we extend an earlier expected constant time algorithm for distance computation between convex polytopes to detect penetrations. The algorithm computes all the contacts between the convex hulls of the polytopes. After identifying the contact regions it traverses the features lying beneath them to more precisely determine the contact regions. The traversal employs a dynamic technique, sweep and prune, to overcome the O(n/sup 2/) pairwise feature checks. The complexity of the overall algorithm is output sensitive. We demonstrate its performance on the dynamic simulation of a threaded insertion.

Some important geometric properties of Support Vector Machines (SVM) have been studied in the last few years, allowing researchers to develop several algorithmic aproaches to the SVM formulation for binary pattern recognition. One important property is the relationship between support vectors and the Convex Hulls of the subsets containing the classes, in the separable case. We propose an algorithm for finding the extreme points of the Convex Hull of the data points in feature space. The key of the method is the construction of the Convex Hull in feature space using an incremental procedure that works using kernel functions and with large datasets. We show some experimental results.

In this paper, we introduce a branch-and-bound algorithm for solving fair division problems with indivisible items. Unlike similar algorithms for this problem, our algorithm is applicable to a wide class of possible fairness criteria. Computational results show that the algorithm exhibits very good performance for a considerable number of problem instances. Main applications of the algorithm are seen in computational studies of fairness criteria and fair division problems. In these problems, a relatively small number of items is considered, so an exact algorithm can be used even though the problem is a generalization of the set partitioning problem, which is NP-complete. An exemplary study comparing Max-min and Nash bargaining solutions to the fair division problem illustrates the use of the algorithm.

The problem of maximizing a convex function on a so-called simple set is considered. Based on the optimality conditions [19], an algorithm for solving the problem is proposed. This numerical algorithm is shown to be convergent. The proposed algorithm has been implemented and tested on a variety of test problems.

After McCallum and Avis [4] showed that the convex hull of a simple polygon P with n vertices can be constructed in O(n) time, several authors [1,2,3] devised simplified algorithms for this prob- lem. Graham and Yao [2] presented a particularly simple and elegant one. After finding two points of the convex hull, their algorithm generated all other hull vertices using only one stack for inter- mediate storage. It is the purpose of this short article to show that a slightly modified version of their algorithm constructs, on-line, the convex hull of any simple polyline in O(n) time. In contrast, the on-line construction of a nonsimple polyline requires O(n log n) time, as shown by Preparata [5]. In the special case of a simple polygon our algorithm produces the convex hull without first identifying two of the hull vertices, as was re- quired in [2]. The price that we pay is the use of a deque instead of a queue. After this article was submitted, we learned of a similar approach taken by Tor and Middleditch [6], who embed it in an algorithm for the convex decomposition of .a sim- ple polygon. To keep this article short, we use where possi- ble the definitions and notations of Graham and Yao. The polyline P = (vl,... , Vm) is assumed to

An algorithm for the formation of the convex hull of a silhouette is described. Input data takes the form of a Freeman chain; arithmetic is limited to integer addition and subtraction. It is shown that the chains of the hull concavities may be readily derived, so facilitating the construction of a feature vector.