Barycentric coordinates for polytopes

In Wachspress (1975) [1], theory was developed for constructing rational basis functions for convex polygons and polyhedra. These barycentric coordinates were positive within the elements. Generalization to higher space dimensions is described here. The GADJ algorithm developed by Dasgupta (2003) [5] and in Dasgupta and Wachspress (2008) [6] is crucial for simple construction of rational barycentric basis functions.     

Contributing vertices-based Minkowski sum computation of convex polyhedra

Minkowski sum is an important operation. It is used in many domains such as: computer-aided design, robotics, spatial planning, mathematical morphology, and image processing. We propose a novel algorithm, named the Contributing Vertices-based Minkowski Sum (CVMS) algorithm for the computation of the Minkowski sum of convex polyhedra. The CVMS algorithm allows to easily obtain all the facets of the Minkowski sum polyhedron only by examining the contributing vertices—a concept we introduce in this work, for each input facet. We exploit the concept of contributing vertices to propose the Enhanced and Simplified Slope Diagram-based Minkowski Sum (ESSDMS) algorithm, a slope diagram-based Minkowski sum algorithm sharing some common points with the approach proposed by Wu et al. [Wu Y, Shah J, Davidson J. Improvements to algorithms for computing the Minkowski sum of 3-polytopes. Comput Aided Des. 2003; 35(13): 1181-92]. The ESSDMS algorithm does not embed input polyhedra on the unit sphere and does not need to perform stereographic projections. Moreover, the use of contributing vertices brings up more simplifications and improves the overall performance. The implementations for the mentioned algorithms are straightforward, use exact number types, produce exact results, and are based on CGAL, the Computational Geometry Algorithms Library. More examples and results of the CVMS algorithm for several convex polyhedra can be found at http://liris.cnrs.fr/hichem.barki/mksum/CVMS-convex.     

Extending Steinitz’s Theorem to Upward Star-Shaped Polyhedra and Spherical Polyhedra

In 1922, Steinitz’s theorem gave a complete characterization of the topological structure of the vertices, edges, and faces of convex polyhedra as triconnected planar graphs. In this paper, we generalize Steinitz’s theorem to non-convex polyhedra. More specifically, we introduce a new class of polyhedra, wider than convex polyhedra, called upward star-shaped polyhedra and spherical polyhedra, and present graph-theoretic characterization for both polyhedra. Upward star-shaped polyhedra are polyhedra where each face is star-shaped, all faces except the bottom face are visible from a view point, and any two faces sharing two vertices are non-coplanar. Spherical polyhedra are non-singular, non-coplanar polyhedra with no holes.     

Exact and efficient construction of Minkowski sums of convex polyhedra with applications

We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in R³. Our implementation is complete in the sense that it does not assume general position. Namely, it can handle degenerate input, and it produces exact results. We also present applications of the Minkowski-sum computation to answer collision and proximity queries about the relative placement of two convex polyhedra in R³. The algorithms use a dual representation of convex polyhedra, and their implementation is mainly based on the Arrangement package of Cgal, the Computational Geometry Algorithm Library. We compare our Minkowski-sum construction with the only three other methods that produce exact results we are aware of. One is a simple approach that computes the convex hull of the pairwise sums of vertices of two convex polyhedra. The second is based on Nef polyhedra embedded on the sphere, and the third is an output-sensitive approach based on linear programming. Our method is significantly faster. The results of experimentation with a broad family of convex polyhedra are reported. The relevant programs, source code, data sets, and documentation are available at http://www.cs.tau.ac.il/~efif/CD and a short movie [Fogel E, Halperin D. Video: Exact Minkowski sums of convex polyhedra. In: Proceedings of 21st annual ACM symposium on computational geometry. 2005. p. 382-3] that describes some of the concepts portrayed in this paper can be downloaded from http://www.cs.tau.ac.il/~efif/CD/Mink3d.avi.     

Finding the intersection of two convex polyhedra

Given two convex polyhedra in three-dimensional space, we develop an algorithm to (i) test whether their intersection is empty, and (ii) if so to find a separating plane, while (iii) if not to find a point in the intersection and explicitly construct their intersection polyhedron. The algorithm runs in timeO (nlogn), where n is the sum of the numbers of vertices of the two polyhedra. The part of the algorithm concerned with (iii) (constructing the intersection) is based upon the fact that if a point in the intersection is known, then the entire intersection is obtained from the convex hull of suitable geometric duals of the two polyhedra taken with respect to this point.     

An Accurate Distance-Calculation Algorithm for Convex Polyhedra

The paper describes an efficient and accurate algorithm to calculate the distance between convex polyhedra. The closest points between two objects can be calculated by simple projections and can be followed continuously in time. The polyhedra are given by the vertices. Interval data are supported. The accuracy of the calculation is explored.     

Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra into Convex Pieces

We present the first exact and robust implementation of the 3D Minkowski sum of two non-convex polyhedra. Our implementation decomposes the two polyhedra into convex pieces, performs pairwise Minkowski sums on the convex pieces, and constructs their union. We achieve exactness and the handling of all degeneracies by building upon 3D Nef polyhedra as provided by Cgal. The implementation also supports open and closed polyhedra. This allows the handling of degenerate scenarios like the tight passage problem in robot motion planning. The bottleneck of our approach is the union step. We address efficiency by optimizing this step by two means: we implement an efficient decomposition that yields a small number of convex pieces, and develop, test and optimize multiple strategies for uniting the partial sums by consecutive binary union operations. The decomposition that we implemented as part of the Minkowski sum is interesting in its own right. It is the first robust implementation of a decomposition of polyhedra into convex pieces that yields at most O(r ²) pieces, where r is the number of edges whose adjacent facets comprise an angle of more than 180 degrees with respect to the interior of the polyhedron. This work was partially supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301.     

Construction of convex continuations for functions defined on a hypersphere

Construction of convex continuations for functions defined on the vertices of some combinatorial polyhedra, in particular the permutation polyhedron and the arrangement polyhedron, has been studied in [1, 2]. Subsequently this result has been generalized to functions defined at the extreme points of an arbitrary polyhedron [3]. For purposes of combinatorial optimization [4-6] it is relevant to consider the existence and construction of convex continuations from continua, in particular, when the function is defined on a hypersphere in thek-dimensional space. Unfortunately, passage to the limit from discrete sets to continua does not produce positive results in this case. We are thus forced to develop special approaches to investigating the existence of convex continuations of functions defined on continua. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 27–36, March–April, 1998.     

On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms

We present a time algorithm finding a minimum feedback vertex set in an undirected graph on n vertices. We also prove that a graph on n vertices can contain at most 1.8638 ⁿ minimal feedback vertex sets and that there exist graphs having 105 ^n/10≈1.5926 ⁿ minimal feedback vertex sets. Preliminary extended abstracts of this paper appeared in the proceedings of SWAT’06 [29] and IWPEC’06 [18]. Additional support of F.V. Fomin, S. Gaspers and A.V. Pyatkin by the Research Council of Norway. The work of A.V. Pyatkin was partially supported by grants of the Russian Foundation for Basic Research (project code 05-01-00395), INTAS (project code 04–77–7173). I. Razgon is supported by Science Foundation Ireland (Grant Number 05/IN/I886).     

IBCD: a fast collision detection algorithm based on image space using OBB

Image‐based collision detection algorithms make efficient use of the graphics rendering hardware and reduce the computational cost of CPU. In this article, a fast collision detection algorithm based on image space is presented, which combines graphics hardware capabilities with a simplified geometric representation (oriented bounding box) in order to rapidly detect collisions between complex objects. The method can deal with arbitrary polyhedra, while preserving the merits of image‐based collision detection algorithms. This is achieved by decomposing the surfaces of an object into a list of convex pieces. High efficiency of the algorithm is obtained by organizing the convex pieces into a binary tree with each node representing a convex piece, and by adopting triangle strip compression. The algorithm has been implemented and compared with related algorithms. Copyright © 2003 John Wiley & Sons, Ltd.     

Assembly sequences for polyhedra

The problem of finding sequences of motions for the assembly of a given object consisting of polyhedral parts arises in assembly planning. We describe an algorithm to compute the set of all translations separating two polyhedra withn vertices inO(n⁴) steps and show that this is optimal. Given an assembly ofk polyhedra with a total ofn vertices, an extension of this algorithm identifies a valid translation and removable subassembly inO(k²n⁴) steps if one exists. Based on the second algorithm, a polynomial-time method for finding a complete assembly sequence consisting of single translations is derived. An implementation incorporates several changes to achieve better average-case performance; experimental results obtained for simple assemblies are described.This research was funded by DARPA Contract N00014-88-K-0620 (Office of Naval Research) and the Stanford Integrated Manufacturing Association (SIMA).     

基于启发式搜索分离向量的凸多面体碰撞检测

碰撞检测是计算机模拟物理过程的基础，在计算机图形学、CAD／CAM、虚拟现实和机器人等领域有着广泛的应用．该文给出了一个新的用于凸多面体碰撞检测的算法——HP-jump．HP-jump建立了一个有效的碰撞检测模型用于报告物体的碰撞，同时提供了一个快速的启发式的策略用于搜索两个凸多面体的分离向量．该算法是利用凸多面体的层次表示来搜索支撑顶点对，用平衡二叉树来记录球面凸多边形的顶点，同时还利用了时间、空间相关性，这些都加速了算法的执行．该文的最后给出了HP-jump与GJK，I-COLLIDE算法的比较．     

Finding the convex hull of a simple polygon

We describe a new algorithm for finding the convex hull of any simple polygon specified by a sequence of m vertices.An earlier convex hull finder of ours is limited to polygons which remain simple (i.e., nonselfintersecting) when locally non-convex vertices are removed. In this paper we amend our earlier algorithm so that it finds with complexity O(m) the convex hull of any simple polygon, while retaining much of the simplicity of the earlier algorithm.     

Convergence of a general iterative scheme for a finite family of asymptotically quasi-nonexpansive mappings in convex metric spaces and applications

In this paper, we introduce the iterative scheme due to Khan, Domlo and Fukhar-ud-din (2008) [8] in convex metric spaces and establish strong convergence of this scheme to a unique common fixed point of a finite family of asymptotically quasi-nonexpansive mappings. As a consequence of our result, we obtain some related convergence theorems. Our results generalize some recent results obtained in [8].     

A comprehensive analysis of degree based condition for Hamiltonian cycles

Since finding whether a graph has a Hamiltonian path or Hamiltonian cycle are both NP-complete problems, researchers have been formulating sufficient conditions that ensure the path or cycle. Rahman and Kaykobad (2005) [2] presented a sufficient condition for determining the existence of Hamiltonian path. Three recent works-Lenin Mehedy, Md. Kamrul Hasan, Mohammad Kaykobad (2007) [3], Rao Li (2006) [4], Shengjia Li, Ruijuan Li, Jinfeng Feng (2007) [5]-further used the same or similar condition to ensure Hamiltonian cycle with some exceptions. The three works, along with their unique findings, have some common results. This paper unifies the results and brings them under Rahman and Kaykobad’s condition.     

Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G=(V,W,E) is convex if there exists an ordering of the vertices of W such that, for each v∈V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|. This work was supported by FAPESP (Proc. 98/06327-0). The first author was also supported by FAPESP (Proc. 96/04505–2), and CNPq/MCT/FINEP (PRONEX project 107/97).     

Determining the Castability of Simple Polyhedra

A polyhedron P is castable if its boundary can be partitioned by a plane into two polyhedral terrains. Castable polyhedra can be manufactured easily using two cast parts, where each cast part can be removed from the object without breaking the cast part or the object. If we assume that the cast parts are each removed by a single translation, it is shown that for a simple polyhedron with n vertices, castability can be decided in time and linear space using a simple algorithm. A more complicated algorithm solves the problem in time and space, for any fixed ε > 0. In the case where the cast parts are to be removed in opposite directions, a simple O(n ² )-time algorithm is presented. Finally, if the object is a convex polyhedron and the cast parts are to be removed in opposite directions, a simple algorithm is presented. Received June 1, 1994; revised May 25, 1995.