International Journal of Computational Geometry & Applications

Given a pair of start and target configurations, each consisting of n pairwise disjoint disks in the plane, what is the minimum number of moves that suffice for transforming the start configuration into the target configuration? In one move a disk slides in the plane without intersecting any other disk, so that its center moves along an arbitrary (open) continuous curve. We discuss efficient algorithms for this task and estimate their number of moves under different assumptions on disk radii. For example, with n congruent disks, moves always suffice for transforming the start configuration into the target configuration; on the other hand, moves are sometimes necessary.

We introduce the concept of multi-directional width-bounded geometric separators and obtain an improved separator for grid graphs. This yields an improved exact algorithm for the protein folding problem in the HP-model. For a grid graph G with n grid points P, there exists a separator A ⊆ P such that A has at most points, and G − A has two disconnected subgraphs each with at most nodes. This improves the previous upper bound of . We also derive a lower bound for such a separator in grid graphs.

We analyze an algorithm based on principal component analysis (PCA) for detecting the dimension k of a smooth manifold from a set P of point samples. The best running time so far is O(d 2^{O(k7log k)}) by Giesen and Wagner after the adaptive neighborhood graph is constructed. Given the adaptive neighborhood graph, the PCA-based algorithm outputs the true dimension in O(d2^O(k)) time, provided that P satisfies a standard sampling condition as in previous results. Our experimental results validate the effectiveness of the approach. A further advantage is that both the algorithm and its analysis can be generalized to the noisy case, in which small perturbations of the samples and a small portion of outliers are allowed.

We introduce a parallel approach to geometric modeling of complex objects and scenes, combining a dataflow streaming of BSP trees with a partition of the object space into independent portions, to be evaluated in parallel with minimal interprocess communication. Binary Space Partition (BSP) is a space index used in graphics for hidden-surface removal and animation. We use BSP trees with fuzzy leaves as a progressive representation of solid meshes. Our approach is implemented as a dataflow with processes that progress concurrently, where each refinement of the input to a process is mapped instantly to a refinement of the output, so that the result is also a stream of progressive refinements. This framework allows for progressive generation of complex geometric parts and large-scale assemblies. We have adapted several graphics techniques, including BSP, boundary polygons, CSG, splines and subdivision methods, to fit into our dataflow graph, where four types of processes produce, transform, combineor consume mesh cells. This approach is scalable over different kinds of HPC hardware and different number of computing nodes, by way of the decomposition of the object space and of the distribution of computational processes. Compiling a generative geometric expression into a dataflow graph is well suited to SMP machines, whereas a space decomposition into independent portions fits well with computing clusters and grids.

Interpolating a piecewise-linear triangulated surface between two polygons lying in parallel planes has attracted a lot of attention in the literature over the past three decades. This problem is the simplest variant of interpolation between parallel slices, which may contain multiple polygons with unrestricted geometries and/or topologies. Its solution has important applications to medical imaging, digitization of objects, geographical information systems, and more. Practically all currently-known methods for surface reconstruction from parallel slices assume a priori the existence of a non-self-intersecting triangulated surface defined over the vertices of the two polygons, which connects them. Gitlin et al. were the first to specify a nonmatable pair of polygons. In this paper we provide proof of the nonmatability of a “simpler” pair of polygons, which is less complex than the example given by Gitlin et al. Furthermore, we provide a family of polygon pairs with unbounded complexity, which we believe to be nonmatable. We also give a few sufficient conditions for polygon matability.