Narrow Results

This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automaton-based representation of the corresponding set of real vectors. The technique is quite general and has been implemented.

In this article, we study the convex hull presentation of a quadratically constrained set. Applying the new result, we solve a kind of quadratically constrained quadratic programming problems, which generalizes many well-studied problems.

The contours and segments of objects in digital images have many important applications. Contour extractions of gray images can be converted into contour extractions of binary images. This paper presents a novel contour-extraction algorithm for binary images and provides a deduction theory for this algorithm. First, we discuss the method used to construct convex hulls of regions of objects. The contour of an object evolves from a convex polygon until the exact boundary is obtained. Second, the projection methods from lines to objects are studied, in which, a polygon iteration method is presented using linear projection. The result of the iteration is the contour of the object region. Lastly, addressing the problem that direct projections probably cannot find correct projection points, an effective discrete ray-projection method is presented. Comparisons with other contour deformation algorithms show that the algorithm in the present paper is very robust with respect to the shapes of the object regions. Numerical tests show that time consumption is primarily concentrated on convex hull computation, and the implementation efficiency of the program can satisfy the requirement of interactive operations.

The number of inner points excluded in an initial convex hull (ICH) is vital to the efficiency getting the convex hull (CH) in a planar point set. The maximum inscribed circle method proposed recently is effective to remove inner points in ICH. However, limited by density distribution of a planar point set, it does not always work well. Although the affine transformation method can be used, it is still hard to have a better performance. Furthermore, the algorithm mentioned above fails to deal with the exceptional distribution: the gravity centroid (GC) of a planar point set is outside or on the edge formed by the extreme points in ICH. This paper considers how to remove more inner points in ICH when GC is inside of ICH and completely process the case which mentioned above. Further, we presented a complete algorithm architecture: (1) using the ellipse and elasticity ellipse methods (EM and EEM) to remove more inner points in ICH and process the cases: GC is inside or outside of ICH. (2) Using the traditional methods to process the situation: the initial centroid is on the edge in ICH. It is adaptive to more data sets than other algorithms. The experiments under seven distributions show that the proposed method performs better than other traditional algorithms in saving time and space.

Automated object measurement is becoming increasingly important due to its ability to reduce manual costs, increase production efficiency, and minimize errors in various fields. In this paper, we present a novel approach to three-dimensional (3D) object measurement based on point cloud modeling. Our method introduces a fast point cloud modeling computation framework consisting of five stages: coordinate centralization, rotation and translation, noise filtering, plane projection, and geometric computation. Furthermore, we propose a fast convex hull optimization algorithm to reduce the high complexity problem of traditional convex hull calculation. Our extensive experiments demonstrate that our approach outperforms existing methods in terms of measurement error rate and time savings, with a maximum time saving of 31.03% under certain error conditions.

A novel character segmentation method for printed documents is proposed in this paper. It is very difficult to process touching, overlapping and broken characters simultaneously. The strategy of our method is to adjust the binarization parameters such that broken characters can be avoided. On the contrary, adjacent characters may spread into each other seriously. Henceforth, the character segmentation problem can be focused on touching-character detection and separation. In the proposed approach, touching characters can be detected using the topological attributes of characters and the typographical relationship between characters. More specifically, the topological attributes are derived from the spatial organization of concave residua contained in the convex hull enclosing the characters. A shortest-path algorithm together with the convex-hull information is used to separate the composite. Since these features based upon the convex hull are insensitive to character fonts and sizes, the touching-character problem of various fonts and sizes can be managed even for heavily touching characters or italic-type overlapping characters without prior slant correction. The proposed method has been applied to extract isolated characters from the contents of technical journals, which contain characters of various fonts and sizes. The promising experimental results prove the practicality and feasibility of the proposed method.

A convex polytope can either be described as convex hull of vertices or as solution set of a finite number of linear inequalities and equations. Whereas both representations are equivalent from a theoretical point of view, they are not when optimization problems over the polytope have to be solved. It is a challenging task to convert one description into the other. In this paper we address the efficient computation of the facet structure of several polytopes associated with combinatorial optimization problems. New results are presented which are of interest for theoretical investigations as well as for practical optimization.

Let S be a set of n points in the plane and CH(S) be the convex hull of S. We consider the problem of constructing an approximate convex hull which contains CH(S) with strong convexity. An ∊-convex δ-superhull of S is a convex polygon P satisfying the following conditions: (1) P has at most O(n) vertices, (2) P contains CH(S), (3) no vertex of P lies farther than δ outside CH(S), and (4) P remains convex even if its vertices are perturbed by as much as ∊. The parameters ∊ and δ represent the strength of convexity of P and the degree of approximation of P to CH(S), respectively. In this paper, we show that there exists an ∊-convex -superhull with at most n vertices for any S and any ∊ ≥ 0 and it can be constructed in O(n log n) time (in O(n) time is S is sorted).

Boundary approximation of planar shapes by circular arcs has quantitative and qualitative advantages compared to using straight-line segments. We demonstrate this by way of three basic and frequent computations on shapes – convex hull, decomposition, and medial axis. In particular, we propose a novel medial axis algorithm that beats existing methods in simplicity and practicality, and at the same time guarantees convergence to the medial axis of the original shape.

We present three results related to dynamic convex hulls:

• A fully dynamic data structure for maintaining a set of n points in the plane so that we can find the edges of the convex hull intersecting a query line, with expected query and amortized update time O(log^1+εn) for an arbitrarily small constant ε > 0. This improves the previous bound of O(log^3/2n).

• A fully dynamic data structure for maintaining a set of n points in the plane to support halfplane range reporting queries in O(log n+k) time with O(polylog n) expected amortized update time. A similar result holds for 3-dimensional orthogonal range reporting. For 3-dimensional halfspace range reporting, the query time increases to O(log²n/log log n + k).

• A semi-online dynamic data structure for maintaining a set of n line segments in the plane, so that we can decide whether a query line segment lies completely above the lower envelope, with query time O(log n) and amortized update time O(n^ε). As a corollary, we can solve the following problem in O(n^1+ε) time: given a triangulated terrain in 3-d of size n, identify all faces that are partially visible from a fixed viewpoint.

We provide a technique to obtain a lower bound for the area of the convex hull of a set of points and a rectangle in the plane, and then apply the resulting estimates to improve the lower bound for the convex case of Moser's Worm problem. Specifically, we show that any convex universal cover for unit arcs has an area of at least 0.232239. We also apply our approach to the universal cover problem for closed unit curves.

We design an algorithm to compute the Newton polytope of the resultant, known as resultant polytope, or its orthogonal projection along a given direction. The resultant is fundamental in algebraic elimination, optimization, and geometric modeling. Our algorithm exactly computes vertex- and halfspace-representations of the polytope using an oracle producing resultant vertices in a given direction, thus avoiding walking on the polytope whose dimension is α - n - 1, where the input consists of α points in ℤⁿ. Our approach is output-sensitive as it makes one oracle call per vertex and per facet. It extends to any polytope whose oracle-based definition is advantageous, such as the secondary and discriminant polytopes. Our publicly available implementation uses the experimental CGAL package triangulation. Our method computes 5-, 6- and 7- dimensional polytopes with 35K, 23K and 500 vertices, respectively, within 2hrs, and the Newton polytopes of many important surface equations encountered in geometric modeling in < 1sec, whereas the corresponding secondary polytopes are intractable. It is faster than tropical geometry software up to dimension 5 or 6. Hashing determinantal predicates accelerates execution up to 100 times. One variant computes inner and outer approximations with, respectively, 90% and 105% of the true volume, up to 25 times faster.

CAT(0) metric spaces and hyperbolic spaces play an important role in combinatorial and geometric group theory. In this paper, we present efficient algorithms for distance problems in CAT(0) planar complexes. First of all, we present an algorithm for answering single-point distance queries in a CAT(0) planar complex. Namely, we show that for a CAT(0) planar complex with n vertices, one can construct in O(n²log n) time a data structure of size O(n²) so that, given a point , the shortest path γ(x, y) between x and the query point y can be computed in linear time. Our second algorithm computes the convex hull of a finite set of points in a CAT(0) planar complex. This algorithm is based on Toussaint's algorithm for computing the convex hull of a finite set of points in a simple polygon and it constructs the convex hull of a set of k points in O(n²log n + nk log k) time, using a data structure of size O(n² + k).

We combine geometric methods with a numerical box search algorithm to show that the minimal area of a convex set in the plane which can cover every closed plane curve of unit length is at least $0.0975$. This improves the best previous lower bound of $0.096694$. In fact, we show that the minimal area of the convex hull of circle, equilateral triangle, and rectangle of perimeter $1$ is between $0.0975$ and $0.09763$.

In this paper, we investigate the problem of finding the common tangents of two convex polygons that intersect in two (unknown) points. First, we give a Θ(log²n) bound for algorithms that store the polygons in independent arrays. Second, we show how to beat the lower bound if the vertices of the convex polygons are drawn from a fixed set of n points. We introduce a data structure called a compact interval tree that supports common tangent computations, as well as the standard binary-search-based queries, in O(logn) time apiece. Third, we apply compact interval trees to solve the subpath hull query problem: given a simple path, preprocess it so that we can find the convex hull of a query subpath quickly. With O(nlogn) preprocessing, we can assemble a compact interval tree that represents the convex hull of a query subpath in O(logn) time. In order to represent arrangements of Lines implicitly, Edelsbrunner et al. used a less efficient structure, called bridge trees, to solve the subpath hull query problem. Our compact interval trees improve their results by a factor of O(logn). Thus, the present paper replaces the paper on bridge trees referred to by Edelsbrunner et al.

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 the problem of constructing the boundary of the union T(S) of all such 3-colored triangles can be done in optimal O(n log n) time.

In this paper we prove the correctness of a “local” criterion for computing the convex hull of the union ( “merging”) of two disjoint convex polyhedra. This criterion is structural. Therefore it can be algorithmically tested in several ways, not necessarily involving the determination of support (tangent) planes; indeed, it can be implemented by just testing for the intersection of certain planes and lines with convex polytopes. This criterion is amenable to parallel implementation and leads to a provably correct algorithm that computes the convex hull of any n points in three-dimensional space in O(log² n) time using O(n) processors on a CREW PRAM.

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² n) time and uses O(nα(n)) space, where d is the size of the final display, and α(n) is a (very slowly growing) functional inverse of Ackermann’s function. Our implementation is especially simple and practical, because we try to take full advantage of the specific geometrical properties of the terrain. The asymptotic speed of our algorithm has been improved upon theoretically by other authors, but at the cost of higher space usage and/or high overhead and complicated code. Our main data structure maintains an implicit representation of the convex hull of a set of points that can be dynamically updated in O(log² n) time. It is especially simple and fast in our application since there are no rebalancing operations required in the tree.

We consider the problem of deriving good approximations of the convex hull of a set of points in the plane in the realistic case that only arbitrary finite approximations of the real valued coordinates can be known. In particular, the algorithm we introduce derives sequences of improved certified approximations converging to the exact solution, at the same time allowing the insertion of new points to the problem instance.

The complexity analysis of the algorithm is performed by referring to a suitable computation model, based on a RAM with logarithmic costs, and the derived space and time bounds are shown to be competitive with respect to current off-line algorithms.

Let S be used to denote a finite set of planar geometric objects. Define a polygon transversal of S as a closed simple polygon that simultaneously intersects every object in S, and a minimum polygon transversal of S as a polygon transversal of S with minimum perimeter. If S is a set of points then the minimum polygon transversal of S is the convex hull of S. However, when the objects in S have some dimension then the minimum polygon transversal and the convex hull may no longer coincide. We consider the case where S is a set of line segments. If the line segments are constrained to lie in a fixed number of orientations we show that a minimum polygon transversal can be found in O(n log n) time. More explicitely, if m denotes the number of line segment orientations, then the complexity of the algorithm is given by O(3^mn+log n). The general problem for line segments is not known to be polynomial nor is it known to be NP-hard.