No description available.

No description available.

Mechanical CAD/CAM (computer aided design/manufacturing) as a field research concerns itself with the algorithms and the mathematics necessary to simulate mechanical parts of the computer, that is to produce a computer model. Solid modelling is a subdiscipline in which the computer model accurately simulates volumetric, i.e. 'solid', properties of mechanical parts. This dissertation deals with a particular type of free-form surface, the blending surface, which is particularly well-suited for solid modelling. A blending surface is one which replaces creases and kinks in the original model with smooth surfaces. A fillet surface is a simple example. We introduce an intuitive paradigm for devising different types of blending forms. Using the paradigm, three forms are derived: the circular, the rolling-ball, and the super-elliptic forms. Important mathematical properties are investigated for the blending surfaces, e.g. continuity, smoothness, containment etc. Blending on blends is introduced as a notion which both extends the flexibility of blending surfaces and allows the blending of multiple surfaces. Blending on blends requires one to think about the way in which the defining functions act as a distance measure from a point in space to a surface. The function defining the super-elliptic blend is offered as an example or a poor distance measure. The zero surface of this function is then embedded within a function which provides an improved distance measure. Mathematical properties are derived for the new function. A weakness in the continuity properties of above blending form is rectified by defining another method to embed the super elliptic blend into a function with better distance properties. This is the displacement form. The concern with this form is its computational reliability which is, therefore, considered in more depth. In the process of integrating the blending surface geometry into a solid modelling environment so it was usable, it was discovered that three other formidable problems needed some type of resolution. These were the topological, the intersection and the display problems. We report on the problems, and solutions which we developed.

Thesis--Auburn University, 2010. / Abstract. Includes bibliographic references (p.28).

No description available.

Approximate convex decomposition (ACD) is a technique that partitions an input object into "approximately convex" components. Decomposition into approximately convex pieces is both more efficient to compute than exact convex decomposition and can also generate a more manageable number of components. It can be used as a basis of divide-and-conquer algorithms for applications such as collision detection, skeleton extraction and mesh generation. In this paper, we propose a new method called Fast Approximate Convex Decomposition (FACD) that improves the quality of the decomposition and reduces the cost of computing it for both 2D and 3D models. In particular, we propose a new strategy for evaluating potential cuts that aims to reduce the relative concavity, rather than absolute concavity. As shown in our results, this leads to more natural and smaller decompositions that include components for small but important features such as toes or fingers while not decomposing larger components, such as the torso that may have concavities due to surface texture. Second, instead of decomposing a component into two pieces at each step, as in the original ACD, we propose a new strategy that uses a dynamic programming approach to select a set of n_c non-crossing (independent) cuts that can be simultaneously applied to decompose the component into n_c + 1 components. This reduces the depth of recursion and, together with a more efficient method for computing the concavity measure, leads to significant gains in efficiency. We provide comparative results for 2D and 3D models illustrating the improvements obtained by FACD over ACD and we compare with the segmentation methods given in the Princeton Shape Benchmark.

This doctoral thesis addresses one major difficulty in formal proof: removing obstructions to intuition which hamper the proof endeavour. We investigate this in the context of formally verifying geometric algorithms using the theorem prover Isabelle, by first proving the Graham’s Scan algorithm for finding convex hulls, then using the challenges we encountered as motivations for the design of a general, modular framework for combining mathematical tools. We introduce our integration framework — the Prover’s Palette, describing in detail the guiding principles from software engineering and the key differentiator of our approach — emphasising the role of the user. Two integrations are described, using the framework to extend Eclipse Proof General so that the computer algebra systems QEPCAD and Maple are directly available in an Isabelle proof context, capable of running either fully automated or with user customisation. The versatility of the approach is illustrated by showing a variety of ways that these tools can be used to streamline the theorem proving process, enriching the user’s intuition rather than disrupting it. The usefulness of our approach is then demonstrated through the formal verification of an algorithm for computing Delaunay triangulations in the Prover’s Palette.

A pair of straight-line drawings of a graph is called parallel if, for every edge of the graph, the line segment that represents the edge in one drawing is parallel with the line segment that represents the edge in the other drawing. We study the problem of morphing between pairs of parallel planar drawings of a graph, keeping all intermediate drawings planar and parallel with the source and target drawings. We call such a morph a parallel morph. Parallel morphs have application to graph visualization. The problem of deciding whether two parallel drawings in the plane admit a parallel morph turns out to be NP-hard in general. However, for some restricted classes of graphs and drawings, we can efficiently decide parallel morphability. Our main positive result is that every pair of parallel simple orthogonal drawings in the plane admits a parallel morph. We give an efficient algorithm that computes such a morph. The number of steps required in a morph produced by our algorithm is linear in the complexity of the graph, where a step involves moving each vertex along a straight line at constant speed. We prove that this upper bound on the number of steps is within a constant factor of the worst-case lower bound. We explore the related problem of computing a parallel morph where edges are required to change length monotonically, i.e. to be either non-increasing or non-decreasing in length. Although parallel orthogonally-convex polygons always admit a monotone parallel morph, deciding morphability under these constraints is NP-hard, even for orthogonal polygons. We also begin a study of parallel morphing in higher dimensions. Parallel drawings of trees in any dimension always admit a parallel morph. This is not so for parallel drawings of cycles in 3-space, even if orthogonal. Similarly, not all pairs of parallel orthogonal polyhedra admit a parallel morph, even if they are topological spheres. In fact, deciding parallel morphability turns out to be PSPACE-hard for both parallel orthogonal polyhedra, and parallel orthogonal drawings in 3-space.

When dealing with massive data sets, standard algorithms may easily ``run out of memory''. In this thesis, we design efficient algorithms in space-conscious models. In particular, in-place algorithms, multi-pass algorithms, read-only algorithms, and stream-sort algorithms are studied, and the focus is on fundamental geometric problems, such as 2D convex hulls, 3D convex hulls, Voronoi diagrams and nearest neighbor queries, Klee's measure problem, and low-dimensional linear programming. In-place algorithms only use O(1) extra space besides the input array. We present a data structure for 2D nearest neighbor queries and algorithms for Klee's measure problem in this model. Algorithms in the multi-pass model only make read-only sequential access to the input, and use sublinear working space and small (usually a constant) number of passes on the input. We present algorithms and lower bounds for many problems, including low-dimensional linear programming and convex hulls, in this model. Algorithms in the read-only model only make read-only random access to the input array, and use sublinear working space. We present algorithms for Klee's measure problem and 2D convex hulls in this model. Algorithms in the stream-sort model use sorting as a primitive operation. Each pass can either sort the data or make sequential access to the data. As in the multi-pass model, these algorithms can only use sublinear working space and a small (usually a constant) number of passes on the data. We present algorithms for constructing convex hulls and polygon triangulation in this model.

A pair of straight-line drawings of a graph is called parallel if, for every edge of the graph, the line segment that represents the edge in one drawing is parallel with the line segment that represents the edge in the other drawing. We study the problem of morphing between pairs of parallel planar drawings of a graph, keeping all intermediate drawings planar and parallel with the source and target drawings. We call such a morph a parallel morph. Parallel morphs have application to graph visualization. The problem of deciding whether two parallel drawings in the plane admit a parallel morph turns out to be NP-hard in general. However, for some restricted classes of graphs and drawings, we can efficiently decide parallel morphability. Our main positive result is that every pair of parallel simple orthogonal drawings in the plane admits a parallel morph. We give an efficient algorithm that computes such a morph. The number of steps required in a morph produced by our algorithm is linear in the complexity of the graph, where a step involves moving each vertex along a straight line at constant speed. We prove that this upper bound on the number of steps is within a constant factor of the worst-case lower bound. We explore the related problem of computing a parallel morph where edges are required to change length monotonically, i.e. to be either non-increasing or non-decreasing in length. Although parallel orthogonally-convex polygons always admit a monotone parallel morph, deciding morphability under these constraints is NP-hard, even for orthogonal polygons. We also begin a study of parallel morphing in higher dimensions. Parallel drawings of trees in any dimension always admit a parallel morph. This is not so for parallel drawings of cycles in 3-space, even if orthogonal. Similarly, not all pairs of parallel orthogonal polyhedra admit a parallel morph, even if they are topological spheres. In fact, deciding parallel morphability turns out to be PSPACE-hard for both parallel orthogonal polyhedra, and parallel orthogonal drawings in 3-space.