共查询到20条相似文献,搜索用时 0 毫秒
1.
Pankaj K. Agarwal Boris Aronov Vladlen Koltun Micha Sharir 《Discrete and Computational Geometry》2005,34(2):231-250
Let B be a set of n unit balls
in ℝ3. We show that the combinatorial complexity of the
space of lines in ℝ3 that avoid all the balls of B is O(n3+ε), for any ε > 0. This result has connections to
problems in visibility, ray shooting, motion planning, and
geometric optimization. 相似文献
2.
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. 相似文献
3.
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. 相似文献
4.
Maria Belk 《Discrete and Computational Geometry》2007,37(2):139-162
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 EN with N ≥ 3, there exists a corresponding configuration in E3 with the same edge lengths. In this paper the two graphs V8 and C5 × C2 are shown to be 3-realizable. As shown by Belk and Connelly, this means that the forbidden minors for 3-realizability are
K5 and K2,2,2.A graph is d-realizable if, for every configuration of its vertices in EN, there exists a another corresponding configuration in Ed with the same edge lengths. 相似文献
5.
Let S be a set of noncrossing triangular obstacles in R 3 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. 相似文献
6.
Oleg R. Musin 《Discrete and Computational Geometry》2006,35(3):375-384
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. 相似文献
7.
Elsa Omaña-Pulido Godfried T. Toussaint 《Journal of Mathematical Modelling and Algorithms》2002,1(4):301-329
Let [a,b] be a line segment with end points a, b and a point at which a viewer is located, all in R
3. 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. 相似文献
8.
9.
Abstract. A dihedral (trihedral) wedge is the intersection of two (resp. three) half-spaces in R
3
. 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
3
. These bounds are not far from being optimal. 相似文献
10.
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
2+), for any > 0. We also show that when the sites are n
segments in 3-space, this complexity is O(n
2 (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
1 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. 相似文献
11.
Esther Ezra 《Discrete and Computational Geometry》2011,45(1):45-64
We show that the combinatorial complexity of the union of n infinite cylinders in ℝ3, 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). 相似文献
12.
Giuseppe Di Battista Ethan Kim Giuseppe Liotta Anna Lubiw Sue Whitesides 《Discrete and Computational Geometry》2012,47(3):461-491
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. 相似文献
13.
We settle some conjectures formulated by A. Claesson and T. Mansour concerning generalized pattern avoidance of permutations. In particular, we solve the problem of the enumeration of permutations avoiding three generalized patterns of type (1, 2) or (2, 1) by using ECO method and a graphical representation of permutations.Received July 15, 2004 相似文献
14.
Abstract. A dihedral (trihedral) wedge is the intersection of two (resp. three) half-spaces in R
3
. 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
3
. These bounds are not far from being optimal. 相似文献
15.
T. Biedl E. Demaine M. Demaine S. Lazard A. Lubiw J. O'Rourke M. Overmars S. Robbins I. Streinu G. Toussaint S. Whitesides 《Discrete and Computational Geometry》2001,26(3):269-281
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. 相似文献
16.
Timothy M. Chan 《Discrete and Computational Geometry》2012,48(1):1-18
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. 相似文献
17.
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. 相似文献
18.
19.
P. L. Várkonyi 《Studies in Applied Mathematics》2013,130(3):295-315
This paper is concerned with the Floating Body Problem of S. Ulam: the existence of objects other than the sphere, which can float in liquid in any orientation. Despite recent results of F. Wegner pointing towards an affirmative answer, a full proof of their existence is still unavailable. For objects with cylindrical symmetry and density 1/2, the conditions of neutral floating are formulated as an initial value problem, for which a unique solution is predicted in certain cases by a suitable generalization of the Picard–Lindelöf theorem. Numerical integration of the initial value problem provides a rich variety of neutrally floating shapes. 相似文献
20.
We show that the number of incidences between m distinct points
and n distinct circles in d, for any d 3,
is O(m6/11n9/11(m3/n)+m2/3n2/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(m4/7n17/21+m2/3n2/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. 相似文献