Narrow Results

We report our experiences with the optimization and parallelization of a discrete element code for convex polyhedra on multi-core machines and introduce a novel variant of the sort-and-sweep neighborhood algorithm. While in theory the whole code in itself parallelizes ideally, in practice the results on different architectures with different compilers and performance measurement tools depend very much on the particle number and optimization of the code. After difficulties with the interpretation of the data for speedup and efficiency are overcome, respectable parallelization speedups could be obtained.

Iterative stencil computations are important in scientific computing and more also in the embedded and mobile domain. Recent publications have shown that tiling schemes that ensure concurrent start provide efficient ways to execute these kernels. Diamond tiling and hybrid-hexagonal tiling are two tiling schemes that enable concurrent start. Both have different advantages: diamond tiling has been integrated in a general purpose optimization framework and uses a cost function to choose among tiling hyperplanes, whereas the greater flexibility with tile sizes for hybrid-hexagonal tiling has been exploited for effective generation of GPU code.

In this paper we undertake a comparative study of these two tiling approaches and propose a hybrid approach that combines them. We analyze the effects of tile size and wavefront choices on tile-level parallelism, and formulate constraints for optimal diamond tile shapes. We then extend, for the case of two dimensions, the diamond tiling formulation into a hexagonal tiling one, which offers both the flexibility of hexagonal tiling and the generality of the original diamond tiling implementation. We also show how to compute tile sizes that maximize the compute-to-communication ratio, and apply this result to compare the best achievable ratio and the associated synchronization overhead for diamond and hexagonal tiling.

We consider a problem that arises in generating three-dimensional models by methods of layered manufacturing: How does one decompose a given model P into a small number of sub-models each of which is a terrain polyhedron? Terrain polyhedra have a base facet such that, for each point of the polyhedron, the line segment joining the point to its orthogonal projection on the base facet lies within the polyhedron. Terrain polyhedra are exactly the class of polyhedral models for which it is possible to construct the model using layered manufacturing (with layers parallel to the base facet), without the need for constructing "supports" (which must later be removed). In order to maximize the integrity of a prototype, one wants to minimize the number of individual sub-models that are manufactured and then glued together.

We show that it is NP-hard to decide if a three-dimensional model P of genus 0 can be decomposed into k terrain polyhedra. We also prove a two-dimensional version of this theorem, for the case in which P is a polygonal region with holes. Both results still hold if we are restricted to isothetic objects and/or axis-parallel layering directions.

A simple polyhedron is weakly-monotonic in direction provided that the intersection of the polyhedron and any plane with normal is simply-connected (i.e. empty, a point, a line-segment or a simple polygon). Furthermore, if the intersection is a convex set, then the polyhedron is said to be weakly-monotonic in the convex sense. Toussaint¹⁰ introduced these types of polyhedra as generalizations of the 2-dimensional notion of monotonicity. We study the following recognition problems:

Given a simple n-vertex polyhedron in 3-dimensions, we present an O(n log n) time algorithm to determine if there exists a direction such that when sweeping over the polyhedron with a plane in direction , the cross-section (or intersection) is a convex set. If we allow multiple convex polygons in the cross-section as opposed to a single convex polygon, then we provide a linear-time recognition algorithm. For simply-connected cross-sections (i.e. the cross-section is empty, a point, a line-segment or a simple polygon), we derive an O(n²) time recognition algorithm to determine if a direction exists.

We then study variations of monotonicity in 2-dimensions, i.e. for simple polygons. Given a simple n-vertex polygon P, we can determine whether or not a line ℓ can be swept over P in a continuous manner but with varying direction, such that any position of ℓ intersects P in at most two edges. We study two variants of the problem: one where the line is allowed to sweep over a portion of the polygon multiple times and one where it can sweep any portion of the polygon only once. Although the latter problem is slightly more complicated than the former since the line movements are restricted, our solutions to both problems run in O(n²) time.

THE SEARCHLIGHT SCHEDULING PROBLEM was first studied in 2-dimensional polygons, where the goal is for point guards in fixed positions to rotate searchlights to catch an evasive intruder. Here the problem is extended to 3-dimensional polyhedra, with the guards now boundary segments who rotate half-planes of illumination.

After carefully detailing the 3-dimensional model, several results are established. The first is a nearly direct extension of the planar one-way sweep strategy using what filling guards, a generalization that succeeds despite there being no well-defined we call notion in 3-dimensional space of planar "clockwise rotation." Next follow two results: every polyhedron with r > 0 reflex edges can be searched by at most r² suitably placed boundary guards, whereas just r edguards suffice if the polyhedron is orthogonal. (Mini-mizing the number of guards to search a given polyhedron is easily seen to be NP-hard.) Finally we show that deciding whether a given set of boundary guards has a successful search schedule is strongly NP-hard. A number of peripheral results are proved en route to these central theorems, and several open problems remain for future work.

We present an algorithm for testing the inscribability of a trivalent polyhedron or, equivalently, testing the circumscribability of a simplicial polyhedron. Our algorithm, which runs in linear time and uses only low-precision integer arithmetic, is based on a purely combinatorial characterization of inscribable trivalent polyhedra.

Algorithms for solid boolean operations are strongly based on classifying points with respect to solids. Several algorithms for solving the point-in- polyhedron problem in Brep schemes have been proposed in the literature. In this context, this paper describes an algorithm for the classification of an arbitrary point in the region dose to a polyhe-dron vertex. The algorithm is simple, has linear complexity and does not suffer from singularities. It performs better than previous algorithms, which would be too expensive in this particular case. The proposed algorithm is especially well suited for Brep schemes including spatial data structures for geometric data localization and searching, for operations on octree and extended octree structures, and for boundary evaluation of CSG trees with polyhedral primitives. Its use in the general point-in-polyhedron classification problem is also discussed. The algorithm is based on an extension to point in unbounded polygon of the kinetic framework of Guibas et al.

In this paper we describe the DCEL system: a geometric software package which implements a polyhedral programming environment. This package enables fast prototyping of geometric algorithms for polyhedra or for polyhedral surfaces. We provide an overview of the system's functionality and demonstrate its use in several applications.

We define and study branched shadows of 4-manifolds as a combination of branched spines of 3-manifolds and of Turaev's shadows. We use these objects to combinatorially represent 4-manifolds equipped with Spin^c-structures and homotopy classes of almost complex structures. We then use branched shadows to study complex 4-manifolds and prove that each almost complex structure on a 4-dimensional handlebody is homotopic to a complex one.

We construct a surface that is obtained from the octahedron by pushing out four of the faces so that the curvature is supported in a copy of the Sierpinski gasket (SG) in each of them, and is essentially the self similar measure on SG. We then compute the bottom of the spectrum of the associated Laplacian using the finite element method on polyhedral approximations of our surface, and speculate on the behavior of the entire spectrum.

In this paper we discuss an algorithm to perform the conversion from the interior to the boundary of d-dimensional polyhedra, where both the d-polyhedron and its (d - 1) boundary faces are represented as BSP trees. This approach allows also to compute the BSP tree of the set intersection between any hyperplane in ε^d and the BSP representation of a d-polyhedron. If such section hyperplane is the affine support of a (d - 1)-face, then a BSP tree of the face is generated. The algorithm may be iteratively applied to compute the k-skeletons of a d-polyhedron.

In this paper we discuss a CSG/BSP algorithm to perform the conversion from the boundary to the interior of d-dimensional polyhedra. Both a d-dimensional polyhedral point-set and its boundary (d - 1)-faces are here represented as BSP trees. In this approach no structure, no ordering and even no orientation is required for such boundary BSP trees. In particular it is shown that the interior point-set may be implicitly represented as the Boolean XOR of unbounded polyhedral "stripes" of dimension d, which are bijectively associated to the (d - 1)-faces of the d-polyhedron. A set of quasi-disjoint convex cells which partitionate the polyhedron interior may be computed by explicitly evaluating such CSG tree with XOR operations on the non-leave nodes and with BSP (stripe) trees on the leave nodes.

In this paper, we discuss the implementation of a cell-based smoothed finite element method (CSFEM) within the commercial finite element software Abaqus. The salient feature of the CSFEM is that it does not require an explicit form of the derivative of the shape functions and there is no need for isoparametric mapping. This implementation is accomplished by employing the user element subroutine (UEL) feature in Abaqus. The details on the input data format together with the proposed user element subroutine, which forms the core of the finite element analysis are given. A few benchmark problems from linear elastostatics in both two and three dimensions are solved to validate the proposed implementation. The developed UELs and the associated input files can be downloaded from https://github.com/nsundar/SFEM_in_Abaqus.

The Cayley-Dickson procedure has been used to construct the root systems of SO(8), SO(9) and the exceptional Lie algebra F₄ in terms of quaternions. The Aut(F₄) has a simple presentation of the form (O, O) ⊕ (O, O)^* where O represents the binary octahedral group. Two sets of quaternionic root system of F₄, symbolically written [F₄, F₄] = F₄ + e₇F₄, describe the octonionic root system of E₈ where the root system of the exceptional Lie algebra E₇ are represented by the imaginary octonions. The automorphism group of the octonionic root system of E₇ preserving the octonion algebra is the Chevalley group G₂(2) where the maximal subgroups of G₂(2) are the automorphism groups of the octonionic root systems of the maximal Lie algebras E₆, SU(2) × SO(12) and SU(8) of E₇. Another pairing of the quaternionic roots of the form [F₄, F₄] = F₄ + σF₄, constitutes the root system of E₈ in terms of icosians where half of the roots describe the roots of the noncrystallographic Coxeter group H₄. The relevance of H₄ to E₈ and the maximal subgroups of H₄ have been discussed. Polyhedral structures obtained from the quaternionic root systems of H₄ are described as the orbits of H₃.