A polyomino is an edge-connected set of squares on the square lattice. In this paper, we improve the Conway-Jensen polyomino-counting algorithm by considering bounding boxes on the square lattice rotated by $$45^\circ $$ instead of on the regular unrotated lattice. This allows us to extend significantly the count of polyominoes from 56 to 70 terms.

Abstract We study the behavior at infinity of the farthest and the higher-order Voronoi diagram of n line segments or lines in a d-dimensional Euclidean space. The unbounded parts of these diagrams can be encoded by a Gaussian map on the sphere of directions $$\mathbb {S}^{d-1}$$ S d - 1 . We show that the combinatorial complexity of the Gaussian map for the order-k Voronoi diagram of n line segments and lines is $$O(\min \{k,n-k\}n^{d-1})$$ O ( min { k , n - k } n d - 1 ) , which is tight for $$n-k=O(1)$$ n - k = O ( 1 ) . This exactly reflects the combinatorial complexity of the unbounded features of these diagrams. All the d-dimensional cells of the farthest Voronoi diagram are unbounded, its $$(d-1)$$ ( d - 1 ) -skeleton is connected, and it does not have tunnels. A d-cell of the Voronoi diagram is called a tunnel if the set of its unbounded directions, represented as points on its Gaussian map, is not connected. In a three-dimensional space, the farthest Voronoi diagram of $$n \ge 2$$ n ≥ 2 lines in general position has exactly $$n(n-1)$$ n ( n - 1 ) three-dimensional cells. The Gaussian map of the farthest Voronoi diagram of line segments and lines can be constructed in $$O(n^{d-1} \alpha (n))$$ O ( n d - 1 α ( n ) ) time, for $$d\ge 4$$ d ≥ 4 , while if $$d=3$$ d = 3 , the time drops to worst-case optimal $$\Theta (n^2)$$ Θ ( n 2 ) . We extend the obtained results to bounded polyhedra and clusters of points as sites.

In this video, we survey some results concerning polyominoes, which are sets of connected cells on the square lattice, and specifically, minimal-perimeter polyominoes, that are polyominoes with the minimal-perimeter from all polyominoes of the same size.

We study the behavior at infinity of the farthest and the higher-order Voronoi diagram of n line segments or lines in a d-dimensional Euclidean space. The unbounded parts of these diagrams can be encoded by a Gaussian map on the sphere of directions S^(d-1). We show that the combinatorial complexity of the Gaussian map for the order-k Voronoi diagram of n line segments or lines is O(min{k,n-k} n^(d-1)), which is tight for n-k = O(1). All the d-dimensional cells of the farthest Voronoi diagram are unbounded, its (d-1)-skeleton is connected, and it does not have tunnels. A d-cell of the Voronoi diagram is called a tunnel if the set of its unbounded directions, represented as points on its Gaussian map, is not connected. In a three-dimensional space, the farthest Voronoi diagram of lines has exactly n^2-n three-dimensional cells, when n >= 2. The Gaussian map of the farthest Voronoi diagram of line segments or lines can be constructed in O(n^(d-1) alpha(n)) time, while if d=3, the time drops to worst-case optimal O(n^2).

A polycube is a face-connected set of cubical cells on ℤ3. To-date, no formulae enumerating polycubes by volume (number of cubes) or perimeter (number of empty cubes neighboring the polycube) are known. We present a few formulae enumerating polycubes with a fixed deviation from the maximum possible perimeter.

This video describes a general framework for computing formulae enumerating polycubes of size n which are proper in n-k dimensions (i.e., spanning all n-k dimensions), for a fixed value of k. (Such formulae are central in the literature of statistical physics in the study of percolation processes and collapse of branched polymers.) The implemented software re-affirmed the already-proven formulae for k <= 3, and proved rigorously, for the first time, the formula enumerating polycubes of size n that are proper in n-4 dimensions.

In this video we show how to enumerate polyominoes on twisted cylinders, and explain how to use them for setting lower bounds on the asymptotic growth rate of polyominoes in the plane.

In this video we present Redelmeier's algorithm for counting polyominoes, its generalization for counting animals on any lattice, and our implementation of a parallel version of it.

In this video we present an algorithm for computing the straight skeleton of a polyhedron in three dimensions.

Abstract We present a novel algorithm for reconstructing a subdivision of the three‐dimensional space (given arbitrarily‐oriented slices of it) into labeled domains. The input to the algorithm is a collection of nonparallel planar cross‐sections of an unknown object, where the sections might cover only portions of the supporting planes. (The information in the rest of these planes is, thus, “unknown.”) Each cross‐section consists of a partition of the plane into closed labeled (“colored”) domains with no restrictions whatsoever on either their geometries or topologies, and without any assumptions about similarities between partitions of different sections. The problem is to reconstruct the original three‐dimensional partition by interpolating simultaneously all the cross‐sections, so that planar domains in the input are connected only to other domains of the same color, no two reconstructed spatial domains intersect, and no unnecessary gaps remain between the reconstructed colored domains. The problem of reconstructing multiple‐labeled domains arises, for example, in medical imaging, where different types of tissues are scanned and reconstructed at the same time. Partial slices are typical, for example, in ultrasound scanning. In this work we use the three‐dimensional straight‐skeleton of the arrangement of the cross‐sections. Since the sections might be partial, cells of the arrangement might be nonconvex. For this we use the unambiguous definition, as well as the implementation of the computation, of the straight skeleton of a three‐dimensional polyhedron that we presented in a recent work [ BEGV08 ]. First, we define these cells and compute their skeleton. Second, we compute overlays of portions of sampled contours in the cross‐sections, using the cell skeletons to guide the reconstruction of the mesh.

In the famous Heilbronn's triangle problem, one aims to find a point set S (say, in the plane), in which the smallest area of a triangle defined by three points of S assumes its maximum. In this video segment we present some variants of the problem. We show a few optimal, or almost optimal, configurations of small numbers of points, and generalize the problem to higher dimensions. Then, we make the distinction between the off-line and on-line versions of the problem, and outline an efficient procedure for attacking the latter version of the problem.

The topic of interpolation between slices has been an intriguing problem for many years, as it offers means to visualize and investigate a three-dimensional object given only by its level sets. A slice consists of multiple non-intersecting simple contours, each defined by a cyclic list of vertices. An interpolation solution matches between a number of such slices (two or more at a time), providing means to create a closed surface connecting these slices, or the equivalent morph from one slice to another.

We study the problem of covering a set of points or polyhedra in R3 with two axis-aligned boxes in order to minimize a function of the measures of the two boxes, such as the sum or the maximum of their volumes. This 2-box cover problem arises naturally in the construction of bounding volume hierarchies, as well as in shape approximation and clustering. Existing algorithms solve the min-max version of the exact problem in quadratic time. Our results are more general, addressing min-max, min-sum and other versions. Our results give the first approximation schemes for the problem, which run in nearly linear time, as well as some new exact algorithms. We give (1+e)-approximation algorithms for minimizing the maximum or sum of volumes (or surface areas, diameters, widths, or girths) of the two boxes in R3. We investigate also the problem of computing balanced coverings, in which each box covers at least a fraction of the input objects, and we discuss the application to constructing provably-good bounding volume hierarchies of polyhedra. We also generalize our results to higher dimension.

We present a diagram that captures containmen information for scalable rotated and ranslated versions of a convex polygon. For a given polygon P and a contact point q in a point set S , the diagram parameterizes possible translations, rotations, and scales of he polygon in order to represent containmen regions for each additional point v ∈ S . We present geometric and combinatorial properties for this diagram, and describe how it can be computed and used for solving several geometric problems.

This paper considers computation of visibility for two-dimensional shapes whose boundaries are C1 continuous curves. We assume we are given a one-parameter family of candidate viewpoints, which may be interior or exterior to the object, and at finite or infinite locations. We consider how to compute whether the whole boundary of the shape is visible from some finite set of viewpoints taken from this family, and if so, how to compute a minimal set of such viewpoints. The viewpoint families we handle include (i) the set of viewing directions from infinity, (ii) viewpoints on a circle located outside the object (for inspection from a turntable), and (iii) viewpoints located on the walls of the shape itself. We compute a structure called a visibility chart, which simultaneously encodes the visible part of the shape's boundary from every view in the family. Using such a visibility chart, finding a minimal set of viewpoints reduces to the set-covering problem over the reals. Practical algorithms are obtained by a discrete sampling of the visibility chart. For exterior visibility problems, a reasonable approach is to compute an almost-optimal solution (in terms of number of viewpoints), which can be done in almost-linear time. For interior visibility problems, or when a more correct solution is required, we solve the general set-covering problem, guaranteeing an optimal solution but taking exponential time.

No abstract available.

No abstract available.

Silhouettes are perceptually and geometrically salient features of geo metric models. Hence a number of graphics and visualization applications need to find them to aid further processing. The efficient computation of silhouettes, especially in the context of perspective projection, is known to be difficult. This paper presents a novel efficient and practical algorithm to compute silhouettes from a sequence of viewpoints under perspective projection. Parallel projection is a special case of this algorithm. Our approach is based on a point-plane duality in three dimensions, which allows an efficient computation of the \emph{changes} in the silhouette of a polygonal model between consecutive frames. In addition, we present several applications of our technique to problems from computer graphics and medical visualization. We also provide experimental data that show the efficiency of our approach.

In this paper we show a lower bound for the generalization of Heilbronn's triangle problem to d dimensions; namely, we show that there exists a set S of n points in the d-dimensional unit cube so that every d+1 points of S define a simplex of volume $\Omega (\frac{1}{n^d})$. We also show a constructive incremental positioning of n points in a unit 3-cube for which every tetrahedron defined by four of these points has volume $\Omega (\frac{1}{n^4})$.

No abstract available.

In this paper we present a new technique for partial surface and volume matching of images in three dimensions. In this problem, we are given two objects in 3-space, each represented as a set of points, scattered uniformly along its boundary or inside its volume. The goal is to find a rigid motion of one object which makes a sufficiently large portion of its boundary lying sufficiently close to a corresponding portion of the boundary of the second object. This is an important problem in pattern recognition and in computer vision, with many industrial, medical, and chemical applications. Our algorithm is based on assigning a directed footprint to every point of the two sets, and locating all the pairs of points (one of each set) whose undirected components of the footprints are sufficiently similar. The algorithm then computes for each such pair of points all the rigid transformations that map the first point to the second, while making the respective direction components of their footprints coincide. A voting scheme is employed for computing transformations which map significantly large number of points of the first set to points of the second set. Experimental results on various examples are presented and show the accurate and robust performance of our algorithm.

We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions.Given an n-vertex polygonal curve P in EL', d 2 3, we approximate P by another polygonal curve P' of m 5 n vertices in IR! such that the vertex sequence of P' is an ordered subsequence of the vertices of P. The goal is to either minimize the size m of P' for a given error tolerance E (called the min-# problem), or to minimize the deviation error E between P and P' for a given size m of P' (called the min-.sproblem).Our techniques enable us to develop efficient nearquadratic-time algorithms in 3-D and sub-cubictime algorithms in 4-D for solving the mm-# and mine problems.We discuss extensions of our solutions to d-dimensional space, where d > 4.

In this paper we describe a geometric software package which serves as a data front-end for rapid prototyping systems. This package can be customized for every layered-manufacturing technique. We survey the full path of data in the system, starting as data files originated from external tools, in most cases CAD systems, going through some repairing operations, then editing a job composed of several objects, and finally processing the job for actual production.

An offset-polygon annulus region is defined in terms of a polygon P and a distance δ > 0 (offset of P). In this paper we solve several containment problems for polygon annulus regions with respect to an input point set. Optimization criteria include both maximizing the number of points contained in a fixed size annulus and minimizing the size of the annulus needed to contain all points. We address the following variants of the problem: placement of an annulus of a convex polygon as well as of a simple polygon; placement by translation only, or by translation and rotation; off-line and on-line versions of the corresponding decision problems; and decision as well as optimization versions of the problems. We present efficient algorithms in each case.

A three-dimensional polygon is triangulable if it has a non-self-intersecting triangulation which defines a simply-connected 2-manifold. We show that the problem of deciding whether a 3-dimensional polygon is triangulable is NP-complete. We then establish some necessary conditions and some sufficient conditions for a polygon to be triangulable, providing special cases when the decision problem may be answered in polynomial time.

We consider the problem of finding a strip separating between two polygons, whose intersection with a third (convex) polygon is of maximum area. We present an optimal linear-time algorithm for computing the optimum strip. When the third polygon is not convex, the running time of the algorithm is quadratic in the size of the input. The application in mind is the piecewise-linear surface interpolation in simple branching cases, where the sought volume branches from one contour in one slice into two contours in the other slice.

The paper presents a system and the associated algorithms for repairing the boundary representation of CAD models. Two types of errors are considered: topological errors, i.e., aggregate errors, like zero volume parts, duplicate or missing parts, inconsistent surface orientation, etc., and geometric errors, i.e., numerical imprecision errors, like cracks or overlaps of geometry. The output of our system describes a set of clean and consistent two-manifolds (possibly with boundaries) with derived adjacencies. Such solid representation enables the application of a variety of rendering and analysis algorithms, e.g., finite element analysis, radiosity computation, model simplification, and solid free form fabrication. The algorithms described were originally designed to correct errors in polygonal B-Reps. We also present an extension for spline surfaces. Central to our system is a procedure for inferring local adjacencies of edges. The geometric representation of topologically adjacent edges are merged to evolve a set of two-manifolds. Aggregate errors are discovered during the merging step. Unfortunately, there are many ambiguous situations where errors admit more than one valid solution. Our system proposes an object repairing process based on a set of user tunable heuristics. The system also allows the user to override the algorithm's decisions in a repair visualization step. In essence, this visualization step presents an organized and intuitive way for the user to explore the space of valid solutions and to select the correct one.

No abstract available.

In this paper we present GeomNet, a system for performing dktributed geometric computing over the Internet.We also provide seved examples of actual geometric algorithms that our system already supports.Application domains for GeomNet include collaborative research and dist ante education.

In this paper we describe a geometric software package which serves as a data front-end for rapid prototyping systems.This package can be customized for every layered-manufacturing technique.We survey the full path of data in the system, starting = data files originated by external tools, in most cases CAD systems, going through some repairing operations, then editing a job composed of several objects, and finally processing the job for actual production.

We describe an algorithm for repairing polyhedral CAD models that have errors in their B-REP. Errors like cracks, degeneracies, duplication, holes and overlaps are usually introduced in solid models due to imprecise arithmetic, model transformations, designer errors, programming bugs, etc. Such errors often hamper further processing such as finite element analysis, radiosity computation and rapid prototyping. Our fault-repair algorithm converts an unordered collection of polygons to a shared-vertex representation to help eliminate errors. This is done by choosing, for each polygon edge, the most appropriate edge to unify it with. The two edges are then geometrically merged into one, by moving vertices. At the end of this process, each polygon edge is either coincident with another or is a boundary edge for a polygonal hole or a dangling wall and may be appropriately repaired. Finally, in order to allow user-inspection of the automatic corrections, we produce a visualization of the repair and let the user mark the corrections that conflict with the original design intent. A second iteration of the correction algorithm then produces a repair that is commensurate with the intent. This, by involving the users in a feedback loop, we are able to refine the correction to their satisfaction.

A three-dimensional polygon is triangulable if it has a non-self-intersecting triangulation which defines a simply-connected 2-manifold. We show that the problem of deciding whether a 3D polygon is triangulable is an NP-complete problem. We then establish some necessary conditions and some sufficient conditions for a polygon to be triangulable, providing special cases when the decision problem may be answered in polynomial time. We also discuss optimal triangulations of 3D polygons. Keywords: three-dimensions, triangulation. 1 Introduction A 3-dimensional polygon is a closed chain of straight segments, where every two successive segments share exactly one point and the intersection of every non-successive pair of segments is empty. A triangulation of a 3-dimensional Work on this paper by the first author has been supported by the Israeli Ministry of Science and the Arts, Eshkol Grant 0562-1-94. Work by the second author has been supported by the funds of the National Science Founda...

No abstract available.

We introduce an algorithm for reconstructing a solid model given a series of planar cross sections. The main contribution of this work is the use of knowledge obtained during the interpolation of neighboring layers while attempting to interpolate a particular layer. This knowledge is used to reconstruct a surface in which consecutive layers are connected smoothly. In most previous work, each layer is interpolated independently of what happened or will happen in the other layers. We also discuss various objective functions which aim to optimize the reconstruction, and present an evaluation of the different objective functions by using various criteria.

Abstract We introduce the boxtree, a versatile data structure for representing triangulated or meshed surfaces in 3D. A boxtree is a hierarchical structure of nested boxes that supports efficient ray tracing and collision detection. It is simple and robust, and requires minimal space. In situations where storage is at a premium, boxtrees are effective alternatives to octrees and BSP trees. They are also more flexible and efficient than R‐trees, and nearly as simple to implement.

In this paper we present a new technique for piecewise-linear surface reconstruction from a series of parallel polygonal cross sections. This is an important problem in medical imaging, surface reconstruction from topographic data, and other applications. We reduce the problem, as in most previous works, to a series of problems of piecewise-linear interpolation between each pair of successive slices. Our algorithm uses a partial curve matching technique for matching parts of the contours, an optimal triangulation of 3-D polygons for resolving the unmatched parts, and a minimum spanning tree heuristic for interpolating between nonsimply connected regions. Unlike previous attempts at solving this problem, our algorithm seems to handle successfully in practice any kind of data. It allows multiple contours in each slice, with any hierarchy of contour nesting, and avoids the introduction of counterintuitive bridges between contours, proposed in some earlier papers to handle interpolation between multiply connected regions. Experimental results on various complex examples, involving actual medical imaging data, are presented and show the good and robust performance of our algorithm.

In this paper we present an algorithm for detecting and repairing defects in the boundary of a polyhedron. These defects, usually caused by problems in CAD software, consist of small gaps bounded by edges that are incident to only one polyhedron face. The algorithm uses a partial curve matching technique for matching parts of the defects, and an optimal triangulation of 3-D polygons for resolving the unmatched parts. It is also shown that finding a consistent set of partial curve matches with maximum score, a subproblem which is related to our repairing process, is NP-hard. Experimental results on several polyhedra are presented.

In this paper we present a new technique for piecewise-linear surface reconstruction from a series of parallel polygonal cross-sections. This is an important problem in medical imaging, surface reconstruction from topographic data, and other applications. We reduce the problem, as in most previous works, to a series of problems of piecewise-linear interpolation between each pair of successive slices. Our algorithm uses a partial curve matching technique for matching parts of the contours, an optimal triangulation of 3-D polygons for resolving the unmatched parts, and a minimum spanning tree heuristic for interpolating between non simply connected regions. Unlike previous attempts at solving this problem, our algorithm seems to handle successfully any kind of data. It allows multiple contours in each slice, with any hierarchy of contour nesting, and avoids the introduction of counter-intuitive bridges between contours, proposed in some earlier papers to handle interpolation between multiply connected regions. Experimental results on various complex examples, involving actual medical imaging data, are presented, and show the good and robust performance of our algorithm.

In this paper we present a new technique for partial surface and volume matching of images in three dimensions. In this problem, we are given two objects in 3-space, each represented as a set of points, scattered uniformly along its boundary or inside its volume. The goal is to find a rigid motion of one object which makes a sufficiently large portion of its boundary lying sufficiently close to a corresponding portion of the boundary of the second object. Our method treats separately the rotation and the translation components of the Euclidean motion that we seek, and compares favorably with previous techniques. Experimental results on various examples, involving data from industrial applications and from molecular biology, are presented and show the accurate performance of our algorithm.