An Accurate Distance Algorithm for Octree‐Encoded Objects

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. Bounding volumes are a common technique; this technique relies on a hierarchical model representation of the two surfaces using axis‐aligned bounding boxes. Formoving objects it is interesting to use unaligned octrees to avoid the wrapping effect that occurs when performing octree decomposition in a common coordinate system after several rotations. We discuss the algorithm for computing accurate enclosures for the distance between objects represented by axis‐aligned or unaligned octrees. This algorithm is based on a new, recently published distance algorithm between two objects represented by axis‐aligned octrees. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Verified convex hull and distance computation for octree-encoded objects

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.     

Computing generalized higher-order Voronoi diagrams on triangulated surfaces

We present an algorithm for computing exact shortest paths, and consequently distance functions, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex triangulated polyhedral surface. The algorithm is generalized to the case when a set of generalized sites is considered, providing their distance field that implicitly represents the Voronoi diagram of the sites. Next, we present an algorithm to compute a discrete representation of the distance function and the distance field. Then, by using the discrete distance field, we obtain the Voronoi diagram of a set of generalized sites (points, segments, polygonal chains or polygons) and visualize it on the triangulated surface. We also provide algorithms that, by using the discrete distance functions, provide the closest, furthest and k-order Voronoi diagrams and an approximate 1-Center and 1-Median.     

Exact join detection for convex polyhedra and other numerical abstractions

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.     

An efficient distance algorithm for interval-based octree-encoded CSG objects with time-space coherence utilization

In this paper, a new distance algorithm for octree-encoded CSG objects is presented. Interval vectors are used to describe the nodes of the octree for a reliable and efficient realization of the hierarchical data structure. The algorithm yields the lower bounds of the distance between the objects and is based on accurate algorithms that have been shown in [1], but involves interval arithmetic for reliable handling of rounding errors. Furthermore, time-space coherence is utilized to increase the efficiency of sequential distance calculations. Experiments validate the approach and show its range of applicability. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Least-squares fitting of circles and ellipses

Fitting circles and ellipses to given points in the plane is a problem that arises in many application areas, e.g., computer graphics, coordinate meteorology, petroleum engineering, statistics. In the past, algorithms have been given which fit circles and ellipses insome least-squares sense without minimizing the geometric distance to the given points.In this paper we present several algorithms which compute the ellipse for which thesum of the squares of the distances to the given points is minimal. These algorithms are compared with classical simple and iterative methods.Circles and ellipses may be represented algebraically, i.e., by an equation of the formF(x)=0. If a point is on the curve, then its coordinates x are a zero of the functionF. Alternatively, curves may be represented in parametric form, which is well suited for minimizing the sum of the squares of the distances.Dedicated to Åke Björck on the occasion of his 60th birthday     

LP-Based Algorithms for Detecting the Collision of Moving Objects

In this paper, we consider the problem of detecting the collision of moving objects in three-dimensional space. We develop two algorithms that use linear programming techniques to detect exact possible collisions between the objects in both time and space when the objects are represented as polyhedral sets in ?² or ?³. The algorithms can handle the case of a rigid body moving on a general path with simultaneous translation and rotation. Computational experience on the developed algorithms is also presented.     

Interval modeling of dynamics for multibody systems

Modeling of multibody systems is an important though demanding field of application for interval arithmetic. Interval modeling of dynamics is particularly challenging, not least because of the differential equations which have to be solved in the process. Most modeling tools transform these equations into a (non-autonomous) initial value problem, interval algorithms for solving of which are known. The challenge then consists in finding interfaces between these algorithms and the modeling tools. This includes choosing between “symbolic” and “numerical” modeling environments, transforming the usually non-autonomous resulting system into an autonomous one, ensuring conformity of the new interval version to the old numerical, etc. In this paper, we focus on modeling multibody systems’ dynamics with the interval extension of the “numerical” environment MOBILE, discuss the techniques which make the uniform treatment of interval and non-interval modeling easier, comment on the wrapping effect, and give reasons for our choice of MOBILE by comparing the results achieved with its help with those obtained by analogous symbolic tools.     

Solving the uncapacitated multi-facility Weber problem by vector quantization and self-organizing maps

The uncapacitated multi-facility Weber problem is concerned with locating m facilities in the Euclidean plane and allocating the demands of n customers to these facilities with the minimum total transportation cost. This is a non-convex optimization problem and difficult to solve exactly. As a consequence, efficient and accurate heuristic solution procedures are needed. The problem has different types based on the distance function used to model the distance between the facilities and customers. We concentrate on the rectilinear and Euclidean problems and propose new vector quantization and self-organizing map algorithms. They incorporate the properties of the distance function to their update rules, which makes them different from the existing two neural network methods that use rather ad hoc squared Euclidean metric in their updates even though the problem is originally stated in terms of the rectilinear and Euclidean distances. Computational results on benchmark instances indicate that the new methods are better than the existing ones, both in terms of the solution quality and computation time.     

Global convergence of a non-convex Douglas–Rachford iteration

We establish a region of convergence for the proto-typical non-convex Douglas–Rachford iteration which finds a point on the intersection of a line and a circle. Previous work on the non-convex iteration Borwein and Sims (Fixed-point algorithms for inverse problems in science and engineering, pp. 93–109, 2011) was only able to establish local convergence, and was ineffective in that no explicit region of convergence could be given.     

ROBUST INEXACT ALTERNATING OPTIMIZATION FOR MATRIX COMPLETION WITH OUTLIERS

We investigate the problem of robust matrix completion with a fraction of observation corrupted by sparsity outlier noise. We propose an algorithmic framework based on the ADMM algorithm for a non-convex optimization, whose objective function consists of an $\ell_1$ norm data fidelity and a rank constraint. To reduce the computational cost per iteration, two inexact schemes are developed to replace the most time-consuming step in the generic ADMM algorithm. The resulting algorithms remarkably outperform the existing solvers for robust matrix completion with outlier noise. When the noise is severe and the underlying matrix is ill-conditioned, the proposed algorithms are faster and give more accurate solutions than state-of-the-art robust matrix completion approaches.     

Planar weber location problems with line barriers

The Weber problem for a given finite set of existing facilities in the plane is to find the location of a new facility such that the weithted sum of distances to the existing facilities is minimized.

A variation of this problem is obtained if the existing facilities are situated on two sides of a linear barrier. Such barriers like rivers, highways, borders or mountain ranges are frequently encountered in practice.

Structural results as well as algorithms for this non-convex optimization problem depending on the distance function and on the number and location of passages through the barrier are presented.     

Polynomial algorithms for solving the quadratic assignment problem on networks

Polynomial algorithms for solving the quadratic assignment problem on special types of networks are proposed. The structure of the links between the objects to be located is represented by a graph.     

Projection Method Approach for General Regularized Non-convex Variational Inequalities

In this paper, we investigate or analyze non-convex variational inequalities and general non-convex variational inequalities. Two new classes of non-convex variational inequalities, named regularized non-convex variational inequalities and general regularized non-convex variational inequalities, are introduced, and the equivalence between these two classes of non-convex variational inequalities and the fixed point problems are established. A projection iterative method to approximate the solutions of general regularized non-convex variational inequalities is suggested. Meanwhile, the existence and uniqueness of solution for general regularized non-convex variational inequalities is proved, and the convergence analysis of the proposed iterative algorithm under certain conditions is studied.     

Dynamics of muscle paths in biomechanical simulations

Within dynamical simulations of biomechanical motion, the actuation of a multibody system (representing bones and joints) can be implemented via Hill-type muscle models. The main task of these models is to describe the typical force-length and force-velocity relation of real muscles. Thus, it is crucial that the muscle path itself, which is dynamically changing during a motion, is represented correctly in the model, because its length and the change of its length in time, i.e. its concentric or eccentric velocity, are related to the scalar value of the muscle force amount and to the direction of the force acting on the multibody system. In our work, we assume that a muscle tone is always present, even at rest, which leads to the conclusion that tendons and muscles are supposed to follow the path of minimal distance between two insertion points not intersecting the bones. This problem can for example be formulated as a constrained nonlinear optimisation problem, or it can be solved with a more efficient algorithm that determines this path as a G1 (geometrical) continuous combination of given curves. Within this work, both procedures are compared concerning the resulting path length and force directions and their computational costs. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A scheme for constructing algorithms for correcting a local perturbation in a finite semimetric

A three-step scheme for constructing algorithms for transforming metric information in data mining is proposed and investigated. The correction problem of a local perturbation of a semimetric on a finite set of objects is considered. In the framework of the proposed scheme, algorithms correcting the changes of the distance between a pair of objects by a given quantity that preserve the metric properties are examined. Sufficient conditions under which the correction of semimetrics using the proposed three-step scheme actually completes in two steps and in some special cases even after the first step are obtained. Semimetric similarity functionals are considered, and the correction algorithms are matched to those functionals.     

Numerical Optimization for the Location of Wastewater Outfalls

In this paper we solve a constrained optimal control problem related to the location of the wastewater outfalls in a sewage disposal system. This is a problem where the control is the position and the constraints are non-convex and pointwise, which makes difficult its resolution. We discretize the problem by means of a characteristics-Galerkin method and we use three algorithms for the numerical resolution of the discretized optimization problem: an interior point algorithm, the Nelder-Mead simplex method and a duality method. Finally, we compare the numerical results obtained by applying the described methods for a realistic problem posed in the ría of Vigo (Galicia, Spain).     

Simulation of Multibody Systems with Nonholonomic Constraints

The paper deals with the nonholonomic multibody system dynamics from a point of view resulting from some present applications in high‐tec areas like high‐speed train technology or biomechanics of some disciplines in high‐performance sports. A formulation of nonholonomic constraints which are linear related to generalized velocities is based on a derivative‐free approach for generating Lagrangian motion equations of multibody systems with kinematical tree structure as well as for constrained multibody systems. This has been done by using di.erential‐geometric concepts in a Riemannian space. The ideas are illustrated by the classical edge condition on double‐curved surfaces. The surfaces are described by C²‐vector functions, for example by NURBS‐approximation. As an example a bobsleigh is regarded moving on a double‐curved surface.     

Link distance and shortest path problems in the plane

This paper describes algorithms to compute Voronoi diagrams, shortest path maps, the Hausdorff distance, and the Fréchet distance in the plane with polygonal obstacles. The underlying distance measures for these algorithms are either shortest path distances or link distances. The link distance between a pair of points is the minimum number of edges needed to connect the two points with a polygonal path that avoids a set of obstacles. The motivation for minimizing the number of edges on a path comes from robotic motions and wireless communications because turns are more difficult in these settings than straight movements.Link-based Voronoi diagrams are different from traditional Voronoi diagrams because a query point in the interior of a Voronoi face can have multiple nearest sites. Our site-based Voronoi diagram ensures that all points in a face have the same set of nearest sites. Our distance-based Voronoi diagram ensures that all points in a face have the same distance to a nearest site.The shortest path maps in this paper support queries from any source point on a fixed line segment. This is a middle-ground approach because traditional shortest path maps typically support queries from either a fixed point or from all possible points in the plane.The Hausdorff distance and Fréchet distance are fundamental similarity metrics for shape matching. This paper shows how to compute new variations of these metrics using shortest paths or link-based paths that avoid polygonal obstacles in the plane.