Narrow Results

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.

Currently, identifying humans using biomechanics-based approaches has gained a lot of significance for person re-identification. Biomechanics-based approaches use knee-hip angle–angle relationships and body movements for person re-identification. Generally, biomechanics of human walking and running is used for person re-identification. In fact, person re-identification is a complex and important task in academia as well as industry and remains an unsolved issue in the computer vision field. The subjects most commonly addressed regarding person re-identification include significant feature extraction that can function accurately with invariant appearance and robust classification. In this study, a significant color feature descriptor is proposed by combining dense color-SIFT and global convex hull salience region features. First convex hull boundary points are detected using the SIFT technique. Furthermore, it is extended with Grubb’s outlier test to eliminate the outlier points detected by SIFT and mark the saliency region via convex hull. Then dense-SIFT and dense-CHF methods are used to extract local and global features within the convex hull region, respectively. Finally, the pre-ranked common nearest neighbor selection technique is applied to minimize overhead of dataset and generate more robust rank classification. The proposed technique is tested using three-camera database video sequences and three publicly available datasets, namely i-LIDS, VIPeR and GRID. Performance of re-identification system is evaluated using a statistical method with CMC curves. The results show better re-identification accuracy in solving the aforementioned problems.

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.

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 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 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 attempt to find counterexamples to the conjecture that the ideal form of a knot, that which minimizes its contour length while respecting a no-overlap constraint, also minimizes the volume of the knot, as determined by its convex hull. We measure the convex hull volume of knots during the length annealing process, identifying local minima in the hull volume that arise due to buckling and symmetry breaking. We use $T(p,2)$ torus knots as an illustrative example of a family of knots whose locally minimal-length embeddings are not necessarily ordered by volume. We identify several knots whose central curve has a convex hull volume that is not minimized in the ideal configuration, and find that $8_{19}$ has a non-ideal global minimum in its convex hull volume even when the thickness of its tube is taken into account.

We present algorithms for computing the kernel of a closed freeform rational surface. The kernel computation is reformulated as a problem of finding the zero-sets of polynomial equations; using these zero-sets we characterize developable surface patches and planar patches that belong to the boundary of the kernel. Using a plane-point duality, this paper also explores a duality relationship between the kernel of a closed surface and the convex hull of its tangential surface.

Let $E\subset {ℝ}^2$ be a closed, bounded set such that $E={\bigcup }_{i=1}^k{E}_i,$ where ${\{E_i\}}_{i=1,\dots ,k}$ is a family of closed convex sets. We establish an estimate from below of the minimal number of the convex components of $E$.

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.

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.