Clamshell Casting

A popular manufacturing technique is clamshell casting, where liquid is poured into a cast and the cast is removed by a rotation once the liquid has hardened. We consider the case where the object to be manufactured is modeled by a polyhedron with combinatorial complexity n of arbitrary genus. The cast consists of exactly two parts and is removed by a rotation around a line in space. The following two problems are addressed: (1) Given a line of rotation l in space, we determine in O(nlog n) time whether there exists a partitioning of the cast into exactly two parts, such that one part can be rotated clockwise around l and the other part can be rotated counterclockwise around l without colliding with the interior of P or the cast. If the problem is restricted further, such a partitioning is only valid when no reflex edge or face of P is perpendicular to l, the algorithm runs in O(n) time. (2) An algorithm running in O(n ⁴log n) time is presented to find all the lines in space that allow a cast partitioning as described above. If we restrict the problem further and find all the lines in space that allow a cast partitioning as described above, such that no reflex edge or face of P is perpendicular to l, the algorithm’s running time becomes O(n ⁴ α(n)). All of the running times are shown to be almost optimal.     

Casting an Object with a Core

This paper addresses geometric problems in manufacturing objects by casting. In casting, molten material is poured into the cavity of the cast and allowed to solidify, after which the cast is removed. The cast has two cast parts to be removed in opposite directions. To manufacture more complicated objects, the cast may also have a side core to be removed in a direction skewed to the removal directions for the cast parts. We address the following problem: Given an object and the removal directions for the cast parts and the side core, can a cast be constructed such that the cast parts and the side core can be removed in the directions specified without colliding with the object or each other? We give necessary and sufficient conditions for the problem, as well as a discrete algorithm to perform the test in O(n ³log?n) time for polyhedral objects, where n is the number of vertices, edges, and facets. If the test result is positive, a cast with complexity O(n ³) can be constructed within the same time bound. We also present an example to show that a cast may have Ω(n ³) complexity in the worst case.     

Casting with Skewed Ejection Direction

Casting is a manufacturing process in which liquid is poured into a cast (mold) that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We address geometric problems concerning the removal of the cast. A cast consists of two parts, one of which retracts in a given direction carrying the object with it. Afterwards, the object will be ejected from the retracted cast part. In this paper we give necessary and sufficient conditions to test the feasibility of the cast part retraction and object ejection, where retraction and ejection directions need not be the same. For polyhedral objects, we show that the test can be performed in O(n² log²n) time and the cast parts can be constructed within the same time bound. The complexity of the cast parts constructed is worst-case optimal. We also give a polynomial-time algorithm for finding a feasible pair of retraction and ejection directions for a given polyhedral object.     

Seven fingers allow force-torque closure grasps on any convex polyhedron

We prove that a robot hand whose fingers make frictionless contact with a convex polyhedral object will be able to find a grasp where the hand can exert any desired force-torque on the object provided the hand has seven fingers. We present an algorithm for grasping any convex polyhedron and we prove rigorously that it works for any convex polyhedron. The algorithm requiresO(n ^3/2logn) steps (in the worst case) wheren is the number of vertices.     

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.     

A parallel sorting algorithm for a novel model of computation

The computational complexity of a parallel algorithm depends critically on the model of computation. We describe a simple and elegant rule-based model of computation in which processors apply rules asynchronously to pairs of objects from a global object space. Application of a rule to a pair of objects results in the creation of a new object if the objects satisfy the guard of the rule. The model can be efficiently implemented as a novel MIMD array processor architecture, the Intersecting Broadcast Machine. For this model of computation, we describe an efficient parallel sorting algorithm based on mergesort. The computational complexity of the sorting algorithm isO(nlog² n), comparable to that for specialized sorting networks and an improvement on theO(n ^1.5) complexity of conventional mesh-connected array processors.     

Algorithms for a Class of Isotonic Regression Problems

The isotonic regression problem has applications in statistics, operations research, and image processing. In this paper a general framework for the isotonic regression algorithm is proposed. Under this framework, we discuss the isotonic regression problem in the case where the directed graph specifying the order restriction is a directed tree with n vertices. A new algorithm is presented for this case, which can be regarded as a generalization of the PAV algorithm of Ayer et al. Using a simple tree structure such as the binomial heap, the algorithm can be implemented in O(n log n) time, improving the previously best known O(n ² ) time algorithm. We also present linear time algorithms for special cases where the directed graph is a path or a star. Received September 2, 1997; revised January 2, 1998, and February 16, 1998.     

A generic algorithm for one-dimensional homotopic compaction

One-dimensional homotopic compaction problems model the task of VLSI layout compaction with automatic jog insertion. They have the following form: given a routable layout, find a layout of minimum width reachable by a continuous motion of layout components that displaces each rigid component horizontally and preserves routability. We define a configuration space for this problem, and prove that if routability is characterized bycut conditions, then the set of reachable configurations is a closed, convex polyhedron. We also present a polynomial-time algorithm that finds the constraints defining this polyhedron and solves them to produce an optimal configuration. A homotopic router can recover the compacted layout from this configuration. We illustrate our strategy in thesketch model of VLSI layout, where it yields a compaction algorithm with worst-case running timeO(N ⁴) on input of sizeN.This paper is based on a thesis submitted in May of 1986 in partial fulfillment of the requirements for the degree of Master of Science in the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. The work described herein was supported in part by a Graduate Fellowship from the Office of Naval Research, in part by the Defense Advanced Research Projects Agency under Contract N00014-80-C-0622, and in part by a Mathematical Sciences Postdoctoral Research Fellowship from the National Science Foundation, Grant DMS-8705835.     

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).     

Detection of rotational and involutional symmetries and congruity of polyhedra

We propose a simple and efficient general algorithm for determining both rotational and involutional symmetries of polyhedra. It requiresO(m ²) time and usesO(m) space, wherem is the number of edges of the polyhedron. As this is the lower bound of the symmetry detection problem for the considered output form, our algorithm is optimal. We show that a slight modification of our symmetry detection algorithm can be used to solve the related conguity problem of polyhedra.     

FEG structures for representation and recognition of 3-D polyhedral objects

The paper proposes a fast O(n ^2.5) recognition algorithm for partially occluded 3D polyhedral objects, where n is the number of the polyhedron vertices.Our approach is based on the generate and test mechanism using the alignment approach as its basic recognition tool. The first stage is to align one face of the unknown polyhedron with one face of one library model (generate). The second stage is a recursive test procedure that checks the matching of the remaining faces. A new structure called FEG—Face Edge Graph is introduced. This structure stores information about the 2D coordinates of each face and the identity of its adjacent faces.A very low complexity is achieved by using a divide and conquer strategy. Instead of trying to recognize the whole object at once, we divide it and conquer (recognize) it face by face. This is done by reducing the recognition problem to generalized subgraph matching problem in which two subgraphs are equal not only when they are isomorphic, but also when they represent the same part of the same object. A special mechanism handles false splitting and false merging of adjacent faces as a result of wrong segmentation.The process lends itself to hierarchical parallel processing in that the matching with each library model may be carried out independently, and also for each model—processing at the pixel level may also be done in parallel.We evaluated our approach with several real range data images as well as some synthetic objects. Four of these cases are reported here.     

Fair versus Unrestricted Bin Packing

Abstract. We consider the on-line Dual Bin Packing problem where we have n unit size bins and a sequence of items. The goal is to maximize the number of items that are packed in the bins by an on-line algorithm. We investigate unrestricted algorithms that have the power of performing admission control on the items, i.e., rejecting items while there is enough space to pack them, versus fair algorithms that reject an item only when there is not enough space to pack it. We show that by performing admission control on the items, we get better performance compared with the performance achieved on the fair version of the problem. Our main result shows that with an unfair variant of First-Fit, we can pack approximately two-thirds of the items for sequences for which an optimal off-line algorithm can pack all the items. This is in contrast to standard First-Fit where we show an asymptotically tight hardness result: if the number of bins can be chosen arbitrarily large, the fraction of the items packed by First-Fit comes arbitrarily close to five-eighths.     

Optimal bounding cones of vectors in three dimensions

The problem of computing the minimum-angle bounding cone of a set of three-dimensional vectors has numerous applications in computer graphics and geometric modeling. One such application is bounding the tangents of space curves or the vectors normal to a surface in the computation of the intersection of two surfaces.No optimal-time exact solution to this problem has been yet given. This paper presents a roadmap for a few strategies that provide optimal or near-optimal (time-wise) solutions to this problem, which are also simple to implement. Specifically, if a worst-case running time is required, we provide an O(nlogn)-time Voronoi-diagram-based algorithm, where n is the number of vectors whose optimum bounding cone is sought. Otherwise, if one is willing to accept an, in average, efficient algorithm, we show that the main ingredient of the algorithm of Shirman and Abi-Ezzi [Comput. Graphics Forum 12 (1993) 261-272] can be implemented to run in optimal Θ(n) expected time. Furthermore, if the vectors (as points on the sphere of directions) are known to occupy no more than a hemisphere, we show how to simplify this ingredient (by reducing the dimension of the problem) without affecting the asymptotic expected running time. Both versions of this algorithm are based on computing (as an LP-type problem) the minimum spanning circle (respectively, ball) of a two-dimensional (respectively, three-dimensional) set of points.     

Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax k vertex-disjoint paths in a directed acyclic graph

This paper is composed of two parts. In the first part, an improved algorithm is presented for the problem of finding length-bounded two vertex-disjoint paths in an undirected planar graph. The presented algorithm requires O(n³bmin) time and O(n²bmin) space, where bmin is the smaller of the two given length bounds. In the second part of this paper, we consider the minmax k vertex-disjoint paths problem on a directed acyclic graph, where k?2 is a constant. An improved algorithm and a faster approximation scheme are presented. The presented algorithm requires O(nk+1Mk−1) time and O(nkMk−1) space, and the presented approximation scheme requires O((1/?)^k−1n2klogk−1M) time and O((1/?)^k−1n2k−1logk−1M) space, where ? is the given approximation parameter and M is the length of the longest path in an optimal solution.     

Finding the intersection of n half-spaces in time O(nlogn)

Given a set of n half-spaces in three dimensional space, we develop an algorithm for finding their common intersection in time O(n log n). The intersection, if nonempty, is presented as a convex polyhedron. The algorithm is summarized as follows: (i) the half-spaces are placed in two sets depending upon whether they contain or do not contain the origin; (ii) the half-spaces in each of these sets are dualized to points, and the convex hulls of the dualized sets are obtained in time O(n log n); (iii) since the half-space intersection is nonempty if and only if these two convex hulls are disjoint, a separating plane is found, also in time O(n log n); (iv) after applying a linear spatial transformation which maps the separating plane to infinity, the convex hull of the union of the two transformed convex hulls is the transformed intersection of the half-spaces. Since the letter can be found in time O(n), the overall running time of the procedure is O(n log n). A significant consequence of this result is that a three-variable linear, or convex, programming problem can be asymptotically solved faster than by the Simplex algorithm, in the worst case.     

Searching a Polygonal Region by a Boundary Searcher

This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually"see"an intruder that is unpredictable and capable of moving arbitrarily fast.A searcher is called the boundary searcher if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time. We present necessary and sufficient conditions for an n-sided polygon to be searchable by a boundary searcher.Based on our characterization,the equivalence of the ...     

VXQR: derivative-free unconstrained optimization based on QR factorizations

This paper presents basic features of a new family of algorithms for unconstrained derivative-free optimization, based on line searches along directions generated from QR factorizations of past direction matrices. Emphasis is on fast descent with a low number of function values, so that the algorithm can be used for fairly expensive functions. The theoretical total time overhead needed per function evaluation is of order O(n ²), where n is the problem dimension, but the observed overhead is much smaller. Numerical results are given for a particular algorithm VXQR1 from this family, implemented in Matlab, and evaluated on the scalability test set of Herrera et al. (, 2010) for problems in dimensions n ∈ {50, 100, 200, 500, 1,000}. Performance depends a lot on the graph {(t,f(x+th)) | t ? [0,1]}\{(t,f(x+th))\mid t\in[0,1]\} of the function along line segments. The algorithm is typically very fast on smooth problems with not too rugged graphs, and on problems with a roughly separable structure. It typically performs poorly on problems where the graph along many directions is highly multimodal without pronounced overall slope (e.g., for smooth functions with superimposed oscillations of significant size), where the graphs along many directions are piecewise constant (e.g., for problems minimizing a maximum norm), or where the function overflows on the major part of the search region and no starting point with finite function value is known.     

Probabilistic Algorithms for Efficient Grasping and Fixturing

Given an object with n points on its boundary where fingers can be placed, we give algorithms to select a ``strong' grasp with the least number c of fingers (up to a logarithmic factor) using several measures of goodness. Along similar lines, given an integer c , we find the ``best' κ c log c finger grasp for a small constant κ . In addition, we generalize existing measures for the case of frictionless assemblies of many objects in contact. We also give an approximation scheme which guarantees a grasp quality close to the overall optimal value where fingers are not restricted to preselected points. These problems translate into a collection of convex set covering problems where we either minimize the cover size or maximize the scaling factor of an inscribed geometric object L . We present an algorithmic framework which handles these problems in a uniform way and give approximation algorithms for specific instances of L including convex polytopes and balls. The framework generalizes an algorithm for polytope covering and approximation by Clarkson [Cla] in two different ways. Let , where d is the dimension of the Euclidean space containing L . For both types of problems, when L is a polytope, we get the same expected time bounds (with a minor improvement), and for a ball, the expected running time is for fixed d , and arbitrary positive δ . We improve this bound if we allow in addition a different kind of approximation for the optimal radius. We also give bounds when d is not a constant. Received November 14, 1996; revised June 20, 1997, and January 9, 1998.