Locked and Unlocked Chains of Planar Shapes

We extend linkage unfolding results from the well-studied case of polygonal linkages to the more general case of linkages of polygons. More precisely, we consider chains of nonoverlapping rigid planar shapes (Jordan regions) that are hinged together sequentially at rotatable joints. Our goal is to characterize the families of planar shapes that admit locked chains, where some configurations cannot be reached by continuous reconfiguration without self-intersection, and which families of planar shapes guarantee universal foldability, where every chain is guaranteed to have a connected configuration space. Previously, only obtuse triangles were known to admit locked shapes, and only line segments were known to guarantee universal foldability. We show that a surprisingly general family of planar shapes, called slender adornments, guarantees universal foldability: roughly, the distance from each edge along the path along the boundary of the slender adornment to each hinge should be monotone. In contrast, we show that isosceles triangles with any desired apex angle <90° admit locked chains, which is precisely the threshold beyond which the slender property no longer holds.     

Efficient Algorithms for Approximating Polygonal Chains

We consider the problem of approximating a polygonal chain C by another polygonal chain C' whose vertices are constrained to be a subset of the set of vertices of C . The goal is to minimize the number of vertices needed in the approximation C' . Based on a framework introduced by Imai and Iri [25], we define an error criterion for measuring the quality of an approximation. We consider two problems. (1) Given a polygonal chain C and a parameter ɛ \geq 0 , compute an approximation of C , among all approximations whose error is at most ɛ , that has the smallest number of vertices. We present an O(n ^{4/3 + δ} ) -time algorithm to solve this problem, for any δ > 0; the constant of proportionality in the running time depends on δ . (2) Given a polygonal chain C and an integer k , compute an approximation of C with at most k vertices whose error is the smallest among all approximations with at most k vertices. We present a simple randomized algorithm, with expected running time O(n ^{4/3 + δ} ) , to solve this problem. Received September 17, 1998, and in revised form July 8, 1999.     

Continuous Forcing Spectra of Even Polygonal Chains

Let G be a graph that admits a perfect matching M.A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G.The cardinality of a forcing set of M with the smallest size is called the forcing number of M,denoted by f(G,M).The forcing spectrum of G is defined as:Spec(G)={f(G,M)|M is a perfect matching of G}.In this paper,by applying the Ztransformation graph(resonance graph)we show that for any polyomino with perfect matchings and any even polygonal chain,their forcing spectra are integral intervals.Further we obtain some sharp bounds on maximum and minimum forcing numbers of hexagonal chains with given number of kinks.Forcing spectra of two extremal chains are determined.     

多边形链图中的完美匹配数

多边形链图的完美匹配数（即多边形碳氢链状聚合物的Ｋｅｋｕｌｅ结构数）是数学化学研究的重要内容之一。我们给出了一个求该数的简洁算法,并证明该数是一个多项式。做为应用,对于一类特殊的多边形链图,给出了具体的表达式。     

多边形螺环链关于Hosoya指标的极值问题

Hosoya指标是化学图论研究中较为流行和重要的拓扑指标之一.首先,根据线性的、无分支的、饱和的多螺环化合物的简单分子结构图定义了"多边形螺环链";其次,研究了多边形螺环链关于Hosoya指标的极值问题;同时,得到了多边形螺环链关于Hosoya指标的排序.     

Realizability of Graphs in Three Dimensions

This paper concludes the characterization of 3-realizable graphs begun by Belk and Connelly. A graph is 3-realizable if, for every configuration of its vertices in E^N with N ≥ 3, there exists a corresponding configuration in E³ with the same edge lengths. In this paper the two graphs V₈ and C₅ × C₂ are shown to be 3-realizable. As shown by Belk and Connelly, this means that the forbidden minors for 3-realizability are K₅ and K_2,2,2.A graph is d-realizable if, for every configuration of its vertices in E^N, there exists a another corresponding configuration in E^d with the same edge lengths.     

Aperture-Angle Optimization Problems in Three Dimensions

Let [a,b] be a line segment with end points a, b and a point at which a viewer is located, all in R ³. The aperture angle of [a,b] from point , denoted by (), is the interior angle at of the triangle (a,b,). Given a convex polyhedron P not intersecting a given segment [a,b] we consider the problem of computing _max() and _min(), the maximum and minimum values of () as varies over all points in P. We obtain two characterizations of _max(). Along the way we solve several interesting special cases of the above problems and establish linear upper and lower bounds on their complexity under several models of computation.     

The Kissing Problem in Three Dimensions

The kissing number k(3) is the maximal number of equal size nonoverlapping spheres in three dimensions that can touch another sphere of the same size. This number was the subject of a famous discussion between Isaac Newton and David Gregory in 1694. The first proof that k(3) = 12 was given by Schutte and van der Waerden only in 1953. In this paper we present a new solution of the Newton--Gregory problem that uses our extension of the Delsarte method. This proof relies on basic calculus and simple spherical geometry.     

Approximating Minimum-Weight Triangulations in Three Dimensions

Let S be a set of noncrossing triangular obstacles in R ³ with convex hull H . A triangulation T of H is compatible with S if every triangle of S is the union of a subset of the faces of T. The weight of T is the sum of the areas of the triangles of T. We give a polynomial-time algorithm that computes a triangulation compatible with S whose weight is at most a constant times the weight of any compatible triangulation. One motivation for studying minimum-weight triangulations is a connection with ray shooting. A particularly simple way to answer a ray-shooting query (``Report the first obstacle hit by a query ray') is to walk through a triangulation along the ray, stopping at the first obstacle. Under a reasonably natural distribution of query rays, the average cost of a ray-shooting query is proportional to triangulation weight. A similar connection exists for line-stabbing queries (``Report all obstacles hit by a query line'). Received February 3, 1997, and in revised form August 21, 1998.     

Lines Avoiding Unit Balls in Three Dimensions

Let B be a set of n unit balls in ℝ³. We show that the combinatorial complexity of the space of lines in ℝ³ that avoid all the balls of B is O(n^3+ε), for any ε > 0. This result has connections to problems in visibility, ray shooting, motion planning, and geometric optimization.     

Lines Avoiding Balls in Three Dimensions Revisited

Let $\mathcal{B}$ be a collection of n arbitrary balls in ?³. We establish an almost-tight upper bound of O(n ^3+?? ), for any ??>0, on the complexity of the space $\mathcal{F}(\mathcal{B})$ of all the lines that avoid all the members of $\mathcal{B}$ . In particular, we prove that the balls of $\mathcal{B}$ admit O(n ^3+?? ) free isolated tangents, for any ??>0. This generalizes the result of Agarwal et al.?(Discrete Comput. Geom. 34:231?C250, 2005), who established this bound only for congruent balls, and solves an open problem posed in that paper. Our bound almost meets the recent lower bound of ??(n ³) of Glisse and Lazard (Proc. 26th Annu. Symp. Comput. Geom., pp. 48?C57, 2010). Our approach is constructive and yields an algorithm that computes the discrete representation of the boundary of $\mathcal{F}(B)$ in O(n ^3+?? ) time, for any ??>0.     

Non-Isotropic Jacobi Spectral and Pseudospectral Methods in Three Dimensions

Non-isotropic Jacobi orthogonal approximation and Jacobi-Gauss type interpolation in three dimensions are investigated. The basic approximation results are established, which serve as the mathematical foundation of spectral and pseudospectral methods for singular problems, as well as problems defined on axisymmetric domains and some unbounded domains. The spectral and pseudospectral schemes are provided for two model problems. Their spectral accuracy is proved. Numerical results demonstrate the high efficiency of suggested algorithms.     

Incidences between Points and Circles in Three and Higher Dimensions

We show that the number of incidences between m distinct points and n distinct circles in ^d, for any d 3, is O(m^6/11n^9/11(m³/n)+m^2/3n^2/3+m+n), where (n)=(log n)^O((n))2 and where (n) is the inverse Ackermann function. The bound coincides with the recent bound of Aronov and Sharir, or rather with its slight improvement by Agarwal et al., for the planar case. We also show that the number of incidences between m points and n unrestricted convex (or bounded-degree algebraic) plane curves, no two in a common plane, is O(m^4/7n^17/21+m^2/3n^2/3+m+n), in any dimension d 3. Our results improve the upper bound on the number of congruent copies of a fixed tetrahedron in a set of n points in 4-space and the lower bound for the number of distinct distances in a set of n points in 3-space. Another application is an improved bound for the number of incidences (or, rather, containments) between lines and reguli in three dimensions. The latter result has already been applied by Feldman and Sharir to obtain a new bound on the number of joints in an arrangement of lines in three dimensions.     

The Union of Congruent Cubes in Three Dimensions

Abstract. A dihedral (trihedral) wedge is the intersection of two (resp. three) half-spaces in R ³ . It is called α-fat if the angle (resp., solid angle) determined by these half-spaces is at least α>0 . If, in addition, the sum of the three face angles of a trihedral wedge is at least γ >4π/3 , then it is called (γ,α)-substantially fat . We prove that, for any fixed γ>4π/3, α>0 , the combinatorial complexity of the union of n (a) α -fat dihedral wedges, and (b) (γ,α) -substantially fat trihedral wedges is at most O(n^ 2+ ɛ ) , for any ɛ >0 , where the constants of proportionality depend on ɛ , α (and γ ). We obtain as a corollary that the same upper bound holds for the combinatorial complexity of the union of n (nearly) congruent cubes in R ³ . These bounds are not far from being optimal.     

Polyhedral Voronoi Diagrams of Polyhedra in Three Dimensions

We show that the complexity of the Voronoi diagram of a collection of disjoint polyhedra in general position in 3-space that have n vertices overall, under a convex distance function induced by a polyhedron with O(1) facets, is O(n ²⁺), for any > 0. We also show that when the sites are n segments in 3-space, this complexity is O(n ² (n) log n). This generalizes previous results by Chew et al. and by Aronov and Sharir, and solves an open problem put forward by Agarwal and Sharir. Specific distance functions for which our results hold are the L ₁ and L _\infty metrics. These results imply that we can preprocess a collection of polyhedra as above into a near-quadratic data structure that can answer -approximate Euclidean nearest-neighbor queries amidst the polyhedra in time O(log (n/) ), for an arbitrarily small > 0.     

On the Union of Cylinders in Three Dimensions

We show that the combinatorial complexity of the union of n infinite cylinders in ℝ³, having arbitrary radii, is O(n ^2+ε ), for any ε>0; the bound is almost tight in the worst case, thus settling a conjecture of Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000), who established a nearly-quadratic bound for the restricted case of nearly congruent cylinders. Our result extends, in a significant way, the result of Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000), in particular, a simple specialization of our analysis to the case of nearly congruent cylinders yields a nearly-quadratic bound on the complexity of the union in that case, thus significantly simplifying the analysis in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000). Finally, we extend our technique to the case of “cigars” of arbitrary radii (that is, Minkowski sums of line-segments and balls) and show that the combinatorial complexity of the union in this case is nearly-quadratic as well. This problem has been studied in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000) for the restricted case where all cigars have (nearly) equal radii. Based on our new approach, the proof follows almost verbatim from the analysis for infinite cylinders and is significantly simpler than the proof presented in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000).     

The Shape of Orthogonal Cycles in Three Dimensions

Let σ be a directed cycle whose edges have each been assigned a desired direction in 3D (East, West, North, South, Up, or Down) but no length. We say that σ is a shape cycle. We consider the following problem. Does there exist an orthogonal representation Γ of σ in 3D space such that no two edges of Γ intersect except at common endpoints and such that each edge of Γ has the direction specified in σ? If the answer is positive, we say that σ is simple. This problem arises in the context of extending orthogonal graph drawing techniques from 2D to 3D. We give a combinatorial characterization of simple shape cycles that yields linear time recognition and drawing algorithms.     

The Union of Congruent Cubes in Three Dimensions

   Abstract. A dihedral (trihedral) wedge is the intersection of two (resp. three) half-spaces in R ³ . It is called α-fat if the angle (resp., solid angle) determined by these half-spaces is at least α>0 . If, in addition, the sum of the three face angles of a trihedral wedge is at least γ >4π/3 , then it is called (γ,α)-substantially fat . We prove that, for any fixed γ>4π/3, α>0 , the combinatorial complexity of the union of n (a) α -fat dihedral wedges, and (b) (γ,α) -substantially fat trihedral wedges is at most O(n^ 2+ ɛ ) , for any ɛ >0 , where the constants of proportionality depend on ɛ , α (and γ ). We obtain as a corollary that the same upper bound holds for the combinatorial complexity of the union of n (nearly) congruent cubes in R ³ . These bounds are not far from being optimal.     

Block Orderings for Tensor-Product Grids in Two and Three Dimensions

We consider two-line and two-plane orderings for a convection–diffusion model problem in two and three dimensions, respectively. These strategies are aimed at introducing dense diagonal blocks, at the price of a slight increase of the bandwidth of the matrix, compared to natural lexicographic ordering. Comprehensive convergence analysis is performed for the block Jacobi scheme. We then move to consider a two-step preconditioning technique, and analyze the numerical properties of the linear systems that are solved in each step of the iterative process. For the 3-dimensional problem this approach is a viable alternative to the Incomplete LU approach, and may be easier to implement in parallel environments. The analysis is illustrated and validated by numerical examples.     

On Levels in Arrangements of Surfaces in Three Dimensions

A favorite open problem in combinatorial geometry is to determine the worst-case complexity of a level in an arrangement. Up to now, nontrivial upper bounds in three dimensions are known only for the linear cases of planes and triangles. We propose the first technique that can deal with more general surfaces in three dimensions. For example, in an arrangement of n ??pseudo-planes?? or ??pseudo-spherical patches?? (where the main criterion is that each triple of surfaces has at most two common intersections), we prove that there are at most O(n ^2.997) vertices at any given level.