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.     

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.     

Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions

We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case. We apply this bound to obtain a near-cubic algorithm for computing a smallest infinite cylinder enclosing a given set of points or balls in 3-space. We also present an approximation algorithm for computing a smallest enclosing cylinder. Received May 23, 1997, and in revised form October 20, 1997.     

Pipes, Cigars, and Kreplach: the Union of Minkowski Sums in Three Dimensions

Let Ω be a set of pairwise-disjoint polyhedral obstacles in R ³ with a total of n vertices, and let B be a ball in R ³. We show that the combinatorial complexity of the free configuration space F of B amid Ω:, i.e., (the closure of) the set of all placements of B at which B does not intersect any obstacle, is O(n ^2+ε ), for any ε >0; the constant of proportionality depends on ε. This upper bound almost matches the known quadratic lower bound on the maximum possible complexity of F . The special case in which Ω is a set of lines is studied separately. We also present a few extensions of this result, including a randomized algorithm for computing the boundary of F whose expected running time is O(n ^2+ε ). Received July 6, 1999, and in revised form April 25, 2000. Online publication August 18, 2000.     

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.     

On NAVIER-STOKES and KELVIN-VOIGT Equations in Three Dimensions in Interpolation Spaces

We show for the three-dimensional initial-boundary value problem of the NAVIER -STOKES and KELVIN -VOIGT equation over bounded domains and for the corresponding stationary problem the existence of weak solutions in intermediate spaces between some of the usual spaces for weak solutions of the NAVIER -STOKES equations and spaces for the corresponding strong solutions. The proofs yield estimates of the solutions in terms of the data which are supposed to be in appropriate intermediate spaces. The basic ingredients of the proof are well-known results for weak and strong solutions and some nonlinear interpolation arguments.     

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.     

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.     

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.     

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.     

三圆柱体垂直相交体积的计算

针对三个直径相同的圆柱体垂直相交所构成的区域,给出求解其体积的积分表达式和积分值,比较不同坐标系下的积分表达式,进一步给出直径不同的三个圆柱体垂直相交所构成的立体体积的积分表达式.     

On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions

We present two new fundamental lower bounds on the worst-case combinatorial complexity of sets of free lines and sets of maximal free line segments in the presence of balls in three dimensions.     

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.     

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 Number of Cylinders Touching a Ball

In this note we prove an upper bound of seven for the maximum number of unit cylinders touching a unit ball in a packing. This improves a previous bound of eight by Heppers and Szab. The value conjectured by Kuperberg in 1990 is six.     

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.     

Locked and Unlocked Polygonal Chains in Three Dimensions

This paper studies movements of polygonal chains in three dimensions whose links are not allowed to cross or change length. Our main result is an algorithmic proof that any simple closed chain that initially takes the form of a planar polygon can be made convex in three dimensions. Other results include an algorithm for straightening open chains having a simple orthogonal projection onto some plane, and an algorithm for making convex any open chain initially configured on the surface of a polytope. All our algorithms require only O(n) basic ``moves.' Received October 9, 1999, and in revised form February 6, 2001, and April 26, 2001. Online publication August 28, 2001.     

关于不变集的维数

本文讨论两类不变集的维数．在第一部分我们研究了平面上的一类自仿集,并给出了它的Hausdorff维数的—个估计．在第二部分我们研究Rd上的迭代函数系(IFS)的不变集, 特别我们考虑了压缩系数不是常数的情形,所得结果给出了经典结果的一个非平凡推广．