We show that the maximum number of geometric permutations of a set of n pairwise-disjoint convex and fat objects in Rd is O(nd-1) . This generalizes the bound of Θ (nd-1) obtained by Smorodinsky et al. [5] on the number of geometric permutations of n pairwise-disjoint balls.
Received August 22, 2000, and in revised form February 6, 2001. Online publication October 12, 2001. 相似文献
Abstract. We prove that a set of n disjoint unit balls in Rd admits at most four distinct geometric permutations, or line transversals, thus settling a long-standing conjecture in combinatorial geometry.
The constant bound significantly improves upon the Θ (nd-1) bound for disjoint balls of unrestricted radii. 相似文献
Abstract. We prove that a set of n disjoint unit balls in Rd admits at most four distinct geometric permutations, or line transversals, thus settling a long-standing conjecture in combinatorial geometry.
The constant bound significantly improves upon the Θ (nd-1) bound for disjoint balls of unrestricted radii. 相似文献
A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position, the edges are represented
by straight line segments connecting the corresponding points.
Improving a result of Pach and T?rőcsik, we show that a geometric graph on n vertices with no k+1 pairwise disjoint edges has at most k3(n+1) edges. On the other hand, we construct geometric graphs with n vertices and approximately (3/2)(k-1)n edges, containing no k+1 pairwise disjoint edges.
We also improve both the lower and upper bounds of Goddard, Katchalski, and Kleitman on the maximum number of edges in a
geometric graph with no four pairwise disjoint edges.
Received May 7, 1998, and in revised form March 24, 1999. 相似文献
Consider an arrangement of n hyperplanes in \reald . Families of convex polytopes whose boundaries are contained in the union of the hyperplanes are the subject of this paper.
We aim to bound their maximum combinatorial complexity. Exact asymptotic bounds were known for the case where the polytopes
are cells of the arrangement. Situations where the polytopes are pairwise openly disjoint have also been considered in the
past. However, no nontrivial bound was known for the general case where the polytopes may have overlapping interiors, for
d>2 . We analyze families of polytopes that do not share vertices. In \real3 we show an O(k1/3n2) bound on the number of faces of k such polytopes. We also discuss worst-case lower bounds and higher-dimensional versions of the problem. Among other results,
we show that the maximum number of facets of k pairwise vertex-disjoint polytopes in \reald is Ω(k1/2 nd/2) which is a factor of away from the best known upper bound in the range nd-2≤ k ≤ nd . The case where 1≤ k ≤ nd-2 is completely resolved as a known Θ(kn) bound for cells applies here.
Received September 20, 1999, and in revised form March 10, 2000. Online publication September 22, 2000. 相似文献
We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log2m log2n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m2+n)log m) andO((m2+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(m/[formula]1+ log2n) time, for any >0. 相似文献
We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem. 相似文献
LetS be a collection ofn convex, closed, and pairwise nonintersecting sets in the Euclidean plane labeled from 1 ton. A pair of permutations $$\left\{ {(i_1 ,i_2 ,...,i_{n - 1} ,i_n ,),(i_n ,i_{n - 1} ,...,i_2 ,i_1 ,)} \right\}$$ is called ageometric permutation of S if there is a line that intersects all sets ofS in this order. We prove thatS can realize at most 2n?2 geometric permutations. This upper bound is tight. 相似文献
Abstract. Two triangles are called almost disjoint if they are either disjoint or their intersection consists of one common vertex. Let f(n) denote the maximum number of pairwise almost disjoint triangles that can be found on some vertex set of n points in 3-space. Here we prove that f(n)=Ω(n3/2) . 相似文献
We construct a family ofn disjoint convex set in d having (n/(d–1))d–1 geometric permutations. As well, we complete the enumeration problem for geometric permutations of families of disjoint translates of a convex set in the plane, settle the case for cubes in d, and construct a family ofd+1 translates in d admitting (d+1)!/2 geometric permutations.This research was partly supported by NSERC Grants A3062, A5137, and A8761. 相似文献
Abstract. Two triangles are called almost disjoint if they are either disjoint or their intersection consists of one common vertex. Let f(n) denote the maximum number of pairwise almost disjoint triangles that can be found on some vertex set of n points in 3-space. Here we prove that f(n)=Ω(n3/2) . 相似文献
Abstract. We show that n arbitrary circles in the plane can be cut into O(n3/2+ɛ) arcs, for any ɛ>0 , such that any pair of arcs intersects at most once. This improves a recent result of Tamaki and Tokuyama [20]. We use this
result to obtain improved upper bounds on the number of incidences between m points and n circles. An improved incidence bound is also obtained for graphs of polynomials of any constant maximum degree. 相似文献
Abstract. We show that n arbitrary circles in the plane can be cut into O(n3/2+ɛ) arcs, for any ɛ>0 , such that any pair of arcs intersects at most once. This improves a recent result of Tamaki and Tokuyama [20]. We use this
result to obtain improved upper bounds on the number of incidences between m points and n circles. An improved incidence bound is also obtained for graphs of polynomials of any constant maximum degree. 相似文献
A special case of a conjecture of Ryser states that if a 3-partite 3-uniform hypergraph has at mostv pairwise disjoint edges then there is a set of vertices of cardinality at most 2v meeting all edges of the hypergraph. The best known upper bound for the size of such a set is (8/3)v, given by Tuza [7]. In this note we improve this to (5/2)v. 相似文献
A line meeting a family of pairwise disjoint convex sets induces two permutations of the sets. This pair of permutations is called a geometric permutation. We characterize the possible triples of geometric permutations for a family of disjoint translates in the plane. Together with earlier studies of geometric permutations this provides a complete characterization of realizable geometric permutations for disjoint translates. 相似文献
A geometric permutation induced by a transversal line of a finite family of disjoint convex sets in ℝd is the order in which the transversal meets the members of the family. It is known that the maximal number of geometric permutations
in families of n disjoint translates of a convex set in ℝ3 is 3. We prove that for d ≥ 3 the maximal number of geometric permutations for such families in ℝd is Ω(n). 相似文献
Let Γ be a collection of unbounded x -monotone Jordan arcs intersecting at most twice each other, which we call pseudoparabolas, since two axis parallel parabolas
intersect at most twice. We investigate how to cut pseudoparabolas into the minimum number of curve segments so that each
pair of segments intersect at most once. We give an Ω( n4/3 ) lower bound and O(n5/3) upper bound on the number of cuts. We give the same bounds for an arrangement of circles. Applying the upper bound, we give
an O(n23/12) bound on the complexity of a level in an arrangement of pseudoparabolas, and an O(n11/6) bound on the complexity of a combinatorially concave chain of pseudoparabolas. We also give some upper bounds on the number
of transitions of the minimum weight matroid base when the weight of each element changes as a quadratic function of a single
parameter.
Received January 17, 1996, and in revised form November 7, 1996. 相似文献
A family of pairwise disjoint compact convex sets is called convexly independent, if none of its members is contained in the convex hull of the union of the other members of the family. The main result of the paper gives an upper bound for the maximum cardinalityh(k, n) of a family of mutually disjoint compact convex sets such that any subfamily of at mostk members of is convexly independent, but no subfamily of sizen is. 相似文献
A disjoint system of type (?, ?, k, n) is a collection ?? = {??1,…, ??m} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair ??i and ??j of distinct members of ?? and for every A ? ??i there exists a B ? ??j that does not intersect A. Let Dn (?, ?, k) denote the maximum possible cardinality of a disjoint system of type (?, ?, k, n). It is shown that for every fixed k ? 2,. This settles a problem of Ahlswede, Cai, and Zhang. Several related problems are considered as well. 相似文献