共查询到20条相似文献,搜索用时 15 毫秒
1.
The tracking of distance between two convex polyhedra is commonly used in the field of robotics, including collision detection or path planning. One of the well-known algorithms in this area is the distance algorithm developed by Gilbert, Johnson and Keerthi. Although this algorithm is widely-used in robotics, up till now, there has been no verification of the computed results. This paper will present an interval version for tracking the distance between convex polyhedra using the C++ library PROFIL/BIAS. 相似文献
2.
F Fernandez J Puerto A M Rodriguez–chia 《The Journal of the Operational Research Society》1997,48(5):479-489
The problem dealt with consists of locating a point in a given convex polyhedron which maximizes the minimum Euclidean distance from a given set of convex polyhedra representing protected areas around population points. The paper describes a finite dominating solution set for the optimal solution and develops a geometrical procedure for obtaining the optimal solution comparing a finite number of candidates. 相似文献
3.
4.
This paper discusses algorithms for computing verified convex hull and distance enclosure for objects represented by axis-aligned or unaligned octrees. To find a convex enclosure of an octree, the concept of extreme vertices of boxes on its boundary has been used. The convex hull of all extreme vertices yields an enclosure of the object. Thus, distance algorithms for convex polyhedra to obtain lower bounds for the distance between two octrees can be applied. Since using convex hulls makes it possible to avoid the unwanted wrapping effect that results from repeated decompositions, it also opens a way to dynamic distance algorithms for moving objects. 相似文献
5.
In this paper we study the representation complexity of a kind of data structure that stores the information necessary to compute the distance from a point to a geometric body. These data structures called adaptive splitting based on cubature distance fields (ASBCDF), are binary search trees generated by the adaptive splitting based on cubature (ASBC) algorithm that adaptively subdivides the space surrounding the body into tetrahedra. Their representation complexity is measured by the number of nodes in the tree (two times the number of tetrahedra in the resulting tessellation). In the case of convex polyhedra we prove that this quantity remains bounded as the number of vertices of the polyhedra increases to infinity. Experimental results show that the number of tetrahedra in the tessellations is almost independent of the combinatorial complexity of the polyhedra. This means that the average compute time of the distance to arbitrary convex polyhedra is almost constant. Therefore, ASBCDFs are especially suitable for real time applications involving rapidly changing environments modelized with complex polyhedra. 相似文献
6.
Given two disjoint convex polyhedra, we look for a best approximation pair relative to them, i.e., a pair of points, one in each polyhedron, attaining the minimum distance between the sets. Cheney and Goldstein showed that alternating projections onto the two sets, starting from an arbitrary point, generate a sequence whose two interlaced subsequences converge to a best approximation pair. We propose a process based on projections onto the half-spaces defining the two polyhedra, which are more negotiable than projections on the polyhedra themselves. A central component in the proposed process is the Halpern–Lions–Wittmann–Bauschke algorithm for approaching the projection of a given point onto a convex set. 相似文献
7.
Deciding whether the union of two convex polyhedra is itself a convex polyhedron is a basic problem in polyhedral computations; having important applications in the field of constrained control and in the synthesis, analysis, verification and optimization of hardware and software systems. In such application fields though, general convex polyhedra are just one among many, so-called, numerical abstractions, which range from restricted families of (not necessarily closed) convex polyhedra to non-convex geometrical objects. We thus tackle the problem from an abstract point of view: for a wide range of numerical abstractions that can be modeled as bounded join-semilattices—that is, partial orders where any finite set of elements has a least upper bound—we show necessary and sufficient conditions for the equivalence between the lattice-theoretic join and the set-theoretic union. For the case of closed convex polyhedra—which, as far as we know, is the only one already studied in the literature—we improve upon the state-of-the-art by providing a new algorithm with a better worst-case complexity. The results and algorithms presented for the other numerical abstractions are new to this paper. All the algorithms have been implemented, experimentally validated, and made available in the Parma Polyhedra Library. 相似文献
8.
Therese Biedl 《Computational Geometry》2011,44(8):409-417
In this paper we study the problem of reconstructing orthogonal polyhedra from a putative vertex set, i.e., we are given a set of points and want to find an orthogonal polyhedron for which this is the set of vertices. This is well-studied in 2D; we mostly focus on 3D, and on the case where the given set of points may be rotated beforehand. We obtain fast algorithms for reconstruction in the case where the answer must be orthogonally convex. 相似文献
9.
ABSTRACTThe article deals with operations defined on convex polyhedra or polyhedral convex functions. Given two convex polyhedra, operations like Minkowski sum, intersection and closed convex hull of the union are considered. Basic operations for one convex polyhedron are, for example, the polar, the conical hull and the image under affine transformation. The concept of a P-representation of a convex polyhedron is introduced. It is shown that many polyhedral calculus operations can be expressed explicitly in terms of P-representations. We point out that all the relevant computational effort for polyhedral calculus consists in computing projections of convex polyhedra. In order to compute projections we use a recent result saying that multiple objective linear programming (MOLP) is equivalent to the polyhedral projection problem. Based on the MOLP solver bensolve a polyhedral calculus toolbox for Matlab and GNU Octave is developed. Some numerical experiments are discussed. 相似文献
10.
《Discrete Mathematics》2007,307(3-5):445-463
Relations between graph theory and polyhedra are presented in two contexts. In the first, the symbiotic dependence between 3-connected planar graphs and convex polyhedra is described in detail. In the second, a theory of nonconvex polyhedra is based on a graph-theoretic foundation. This approach eliminates the vagueness and inconsistency that pervade much of the literature dealing with polyhedra more general than the convex ones. 相似文献
11.
David G. L. Wang 《Geometriae Dedicata》2013,164(1):385-393
A famous problem in discrete geometry is to find all monohedral plane tilers. It is still open to the best of our knowledge. This paper is concerned with one of its variants, that of determining all convex polyhedra whose every cross-section tiles the plane. We call such polyhedra universal tilers. We obtain that a convex polyhedron is a universal tiler only if it is a tetrahedron or a pentahedron. 相似文献
12.
《European Journal of Operational Research》1999,114(1):178-187
The problem of finding the distance to a reverse (or complement of a) convex subset in a normed vector space is considered. This nonconvex and, in general, nonsmooth optimization problem arises in quantitative economics in the theory of measuring the technical efficiency of production units. In this context, applying a suitable duality theorem similar to the Nirenberg's one known for the distance to a convex subset, the problem reduces to a finite number of independent linear programming problems. 相似文献
13.
《Computational Geometry》2000,15(1-3):51-68
This paper presents the Hierarchical Walk, or H-Walk algorithm, which maintains the distance between two moving convex bodies by exploiting both motion coherence and hierarchical representations. For convex polygons, we prove that H-Walk improves on the classic Lin–Canny and Dobkin–Kirkpatrick algorithms. We have implemented H-Walk for moving convex polyhedra in three dimensions. Experimental results indicate that, unlike previous incremental distance computation algorithms, H-Walk adapts well to variable coherence in the motion and provides consistent performance. 相似文献
14.
Certification aspects of the fast gradient method for solving the dual of parametric convex programs
Stefan Richter Colin Neil Jones Manfred Morari 《Mathematical Methods of Operations Research》2013,77(3):305-321
This paper examines the computational complexity certification of the fast gradient method for the solution of the dual of a parametric convex program. To this end, a lower iteration bound is derived such that for all parameters from a compact set a solution with a specified level of suboptimality will be obtained. For its practical importance, the derivation of the smallest lower iteration bound is considered. In order to determine it, we investigate both the computation of the worst case minimal Euclidean distance between an initial iterate and a Lagrange multiplier and the issue of finding the largest step size for the fast gradient method. In addition, we argue that optimal preconditioning of the dual problem cannot be proven to decrease the smallest lower iteration bound. The findings of this paper are of importance in embedded optimization, for instance, in model predictive control. 相似文献
15.
Claudio Mirolo 《Journal of Algorithms in Cognition, Informatics and Logic》1998,26(2):209-237
This article discusses a discrete version of the convex minimization problem with applications to the efficient computation of proximity measures for pairs of convex polyhedra. Given ad-variate convex function and an isothetic grid of sizeO(nd) in d, which is supposed to be finite but not necessarily regular, we want to find the grid cell containing the minimum point. With this aim, we identify a class of elementary subproblems, each resulting in the determination of a half-space in d, and show that the minimization problem can be solved by computingO(log n) half-spaces in the worst case foralmost uniformgrids of fixed dimensiondandO(log n) half-planes in the average for arbitrary planar grids. A major point is the potential of the approach to uniformly solve distance related problems for different configurations of a pair of convex bodies. In this respect, the case of a bivariate function is of particular interest and leads to a fast algorithm for detecting collisions between two convex polyhedra in three dimensions. The collision algorithm runs inO(log2 n) average time for polyhedra withO(n) vertices whose boundaries are suitably represented; more specifically, the 1-skeletons can be embedded into layered Directed Acyclic Graphs which require justO(n) storage. The article ends with a brief discussion of a few experimental results. 相似文献
16.
T. I. Belykh V. P. Bulatov E. N. Yas’kova 《Computational Mathematics and Mathematical Physics》2008,48(1):16-29
Chebyshev points of bounded convex sets, search algorithms for them, and various applications to convex programming are considered for simple approximations of reachable sets, optimal control, global optimization of additive functions on convex polyhedra, and integer programming. The problem of searching for Chebyshev points in multicriteria models of development and operation of electric power systems is considered. 相似文献
17.
Josef Nedoma 《Linear and Multilinear Algebra》1998,44(1):29-44
It is well-known that the solution set of an interval linear equation system is a union of convex polyhedra the number of which increases, in general, exponentially with the problem size. As a consequence, the problem of finding the interval hull of the solution set is NP-hard as J. Rohn and V. Kreinovich proved in [13]. The purpose of this paper is to show that the solution set analysis can be simplified substantially provided the rank of the error matrix is restricted even if the assumption of interval character of data errors is replaced by a more general one. Especially, in the case of a rank-one error matrix we have to look into at most two convex subsets. Besides, a dual approach to describing the solution set is discussed. The original version of this approach was suggested in [7]. 相似文献
18.
In this note, the 80 non‐isomorphic triple systems on 15 points are revisited from the viewpoint of the convex hull of the characteristic vectors of their blocks. The main observation is that the numbers, of facets of these 80 polyhedra are all different, thus producing a new proof of the non‐isomorphism of these triple systems. The space dimension of these polyhedra is also discussed. Finally, we observe the large number of facets of some of these polyhedra with few vertices, in relation with the upper bound problem for combinatorial polyhedra. © 2005 Wiley Periodicals, Inc. J Combin Designs. 相似文献
19.
Stephen E. Wright 《Discrete and Computational Geometry》2010,43(2):467-476
Whenever two nonempty convex polyhedra can be properly separated, a separating hyperplane may be chosen to contain a face
of either polyhedron. It is demonstrated that, in fact, one or the other of the polyhedra admits such an exposed face having
dimension no smaller than approximately half the larger dimension of the two polyhedra. An example shows that the bound on
face dimension is optimal, and a linear programming representation of the problem is given. 相似文献
20.
Distance algorithms are most frequently used in robotics to determine the distance between two obstacles in the environment of a robot or between a sensor point and an object. We extend the multibody simulation package MOBILE for an application of accurate algorithms for distance computation between objects represented by convex or non-convex polyhedra. These objects are represented by their vertices and oriented facets. As an application example, a multibody system is discussed where a sensor point moves close to a non-convex obstacle. The computed results show that the algorithms developed are suitable for accurate real-time multibody simulations. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献