Vertical decompositions for triangles in 3-space

We prove that, for any constant ɛ>0, the complexity of the vertical decomposition of a set ofn triangles in three-dimensional space isO(n ^2+ɛ +K), whereK is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is shown to beO(n ^2+ɛ ). These bounds are almost tight in the worst case. We also give a deterministic output-sensitive algorithm for computing the vertical decomposition that runs inO(n ² logn+V logn) time, whereV is the complexity of the decomposition. The algorithm is reasonably simple (in particular, it tries to perform as much of the computation in two-dimensional spaces as possible) and thus is a good candidate for efficient implementations. The algorithm is extended to compute the vertical decomposition of arrangements ofn algebraic surface patches of constant maximum degree in three-dimensional space in timeO(nλ _q (n) logn +V logn), whereV is the combinatorial complexity of the vertical decomposition, λ _q (n) is a near-linear function related to Davenport-Schinzel sequences, andq is a constant that depends on the degree of the surface patches and their boundaries. We also present an algorithm with improved running time for the case of triangles which is, however, more complicated than the first algorithm. Mark de Berg was supported by the Dutch Organization for Scientific Research (N.W.O.), and by ESPRIT Basic Research Action No. 7141 (project ALCOM II:Algorithms and Complexity). Leonidas Guibas was supported by NSF Grant CCR-9215219, by a grant from the Stanford SIMA Consortium, by NSF/ARPA Grant IRI-9306544, and by grants from the Digital Equipment, Mitsubishi, and Toshiba Corporations. Dan Halperin was supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. A preliminary version of this paper appeared inProc. 10th ACM Symposium on Computational Geometry, 1994, pp. 1–10.     

Geometric Lower Bounds for Parametric Matroid Optimization

We relate the sequence of minimum bases of a matroid with linearly varying weights to three problems from combinatorial geometry: k -sets, lower envelopes of line segments, and convex polygons in line arrangements. Using these relations we show new lower bounds on the number of base changes in such sequences: Ω(nr ^1/3 ) for a general n -element matroid with rank r , and Ω(mα(n)) for the special case of parametric graph minimum spanning trees. The only previous lower bound was Ω(n log r) for uniform matroids; upper bounds of O(mn ^1/2 ) for arbitrary matroids and O(mn ^1/2 / log ^* n) for uniform matroids were also known. Received November 12, 1996, and in revised form February 19, 1997.     

Visibility with Multiple Reflections

We show that the region lit by a point light source inside a simple n -gon after at most k reflections off the boundary has combinatorial complexity O(n ^2k ) , for any k≥ 1 . A lower bound of Ω ((n/k-Θ(1)) ^2k ) is also established which matches the upper bound for any fixed k . A simple near-optimal algorithm for computing the illuminated region is presented, which runs in O(n ^2k log n) time and O(n ^2k ) space for k>1 , and in O(n ² log ² n) time and O(n ² ) space for k=1 . Received March 14, 1996, and in revised form December 22, 1997, and January 5, 1998.     

Sharp Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions

We prove tight and near-tight combinatorial complexity bounds for vertical decompositions of arrangements of hyperplanes and 3-simplices in four dimensions. In particular, we prove a tight upper bound of (n⁴) for the vertical decomposition of an arrangement of n hyperplanes in four dimensions, improving the best previously known bound [8] by a logarithmic factor. We also show that the complexity of the vertical decomposition of an arrangement of n 3-simplices in four dimensions is O(n⁴ (n) log² n), where (n) is the inverse Ackermann function, improving the best previously known bound [2] by a near-linear factor.     

The unbounded-error communication complexity of symmetric functions

We prove an essentially tight lower bound on the unbounded-error communication complexity of every symmetric function, i.e., f(x,y)=D(|x∧y|), where D: {0,1,…,n}→{0,1} is a given predicate and x,y range over {0,1} ⁿ . Specifically, we show that the communication complexity of f is between Θ(k/log⁵ n) and Θ(k logn), where k is the number of value changes of D in {0,1,…, n}. Prior to this work, the problem was solved only for the parity predicate D (Forster 2001).     

Almost linear upper bounds on the length of general davenport—schinzel sequences

Davenport—Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We obtain almost linear upper bounds on the length λ_s(n) of Davenport—Schinzel sequences composed ofn symbols in which no alternating subsequence is of length greater thans+1. These bounds are of the formO(nα(n)^O(α(n)5-3)), and they generalize and extend the tight bound Θ(nα(n)) obtained by Hart and Sharir for the special cases=3 (α(n) is the functional inverse of Ackermann’s function), and also improve the upper boundO(n log*n) due to Szemerédi. Work on this paper has been supported in part by a grant from the U.S. — Israeli Binational Science Foundation.     

Arrangements of segments that share endpoints: Single face results

We provide new combinatorial bounds on the complexity of a face in an arrangement of segments in the plane. In particular, we show that the complexity of a single face in an arrangement ofn line segments determined byh endpoints isO(h logh). While the previous upper bound,O(nα(n)), is tight for segments with distinct endpoints, it is far from being optimal whenn=Ω(h ²). Our results show that, in a sense, the fundamental combinatorial complexity of a face arises not as a result of the number ofsegments, but rather as a result of the number ofendpoints. The research of E. M. Arkin was partially supported by NSF Grants ECSE-8857642 and CCR-9204585. K. Kedem's research was partially supported by AFOSR Grant AFOSR-91-0328. The research of J. S. B. Mitchell was partially supported by a grant from Boeing Computer Services, Hughes Research Laboratories, AFOSR Grant AFOSR-91-0328, and by NSF Grants ECSE-8857642 and CCR-9204585.     

The monotone circuit complexity of boolean functions

Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of sizes in a graphm vertices requires monotone circuits of size Ω(m ^s /(logm)^2s ) for fixeds, and sizem ^Ω(logm) form/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/logm)^2/3 requires monotone circuits exp (Ω((m/logm)^1/3)). For fixeds, any monotone circuit that detects cliques of sizes requiresm) ^s ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function ofn variables is exp (Ω(n ^1/4 · (logn)^1/2)), improving a recent result of exp (Ω(n ^1/8-ε)) due to Andreev. First author supported in part by Allon Fellowship, by Bat Sheva de-Rotschild Foundation by the Fund for basic research administered by the Israel Academy of Sciences. Second author supported in part by a National Science Foundation Graduate Fellowship.     

Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions

The combinatorial complexity of the Voronoi diagram ofnlines in three dimensions under a convex distance function induced by a polytope with a constant number of edges is shown to beO(n²α(n)log n), where α(n) is a slowly growing inverse of the Ackermann function. There are arrangements ofnlines where this complexity can be as large as Ω(n²α(n)).     

Almost tight upper bounds for lower envelopes in higher dimensions

We consider the problem of bounding the combinatorial complexity of the lower envelope ofn surfaces or surface patches ind-space (d≥3), all algebraic of constant degree, and bounded by algebraic surfaces of constant degree. We show that the complexity of the lower envelope ofn such surface patches isO(n ^d−1+∈), for any ∈>0; the constant of proportionality depends on ∈, ond, ons, the maximum number of intersections among anyd-tuple of the given surfaces, and on the shape and degree of the surface patches and of their boundaries. This is the first nontrivial general upper bound for this problem, and it almost establishes a long-standing conjecture that the complexity of the envelope isO(n ^d-2λ _q (n)) for some constantq depending on the shape and degree of the surfaces (where λ _q (n) is the maximum length of (n, q) Davenport-Schinzel sequences). We also present a randomized algorithm for computing the envelope in three dimensions, with expected running timeO(n ^2+∈), and give several applications of the new bounds. Work on this paper has been supported by NSF Grant CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Onk-sets in arrangements of curves and surfaces

We extend the notion ofk-sets and (≤k)-sets (see [3], [12], and [19]) to arrangements of curves and surfaces. In the case of curves in the plane, we assume that each curve is simple and separates the plane. Ak-point is an intersection point of a pair of the curves which is covered by exactlyk interiors of (or half-planes bounded by) other curves; thek-set is the set of allk-points in such an arrangement, and the (≤k)-set is the union of allj-sets, forj≤k. Adapting the probabilistic analysis technique of Clarkson and Shor [13], we obtain bounds that relate the maximum size of the (≤k)-set to the maximum size of a 0-set of a sample of the curves. Using known bounds on the size of such 0-sets we obtain asympotically tight bounds for the maximum size of the (≤k)-set in the following special cases: (i) If each pair of curves intersect at most twice, the maximum size is Θ(nkα(nk)). (ii) If the curves are unbounded arcs and each pair of them intersect at most three times, then the maximum size is Θ(nkα(n/k)). (iii) If the curves arex-monotone arcs and each pair of them intersect in at most some fixed numbers of points, then the maximum size of the (≤k)-set is Θ(k ²λ _s (nk)), where λ _s (m) is the maximum length of (m,s)-Davenport-Schinzel sequences. We also obtain generalizations of these results to certain classes of surfaces in three and higher dimensions. Finally, we present various applications of these results to arrangements of segments and curves, high-order Voronoi diagrams, partial stabbing of disjoint convex sets in the plane, and more. An interesting application yields andO(n logn) bound on the expected number of vertically visible features in an arrangement ofn horizontal discs when they are stacked on top of each other in random order. This in turn leads to an efficient randomized preprocessing ofn discs in the plane so as to allow fast stabbing queries, in which we want to report all discs containing a query point. Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD—the Israeli National Council for Research and Development-and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences.     

Piecewise linear paths among convex obstacles

Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ ^d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n ^{(d−1)[d/2+1]}) segments. The bound cannot be improved below Ω(n ^d ); thus, in ℝ³, the answer is betweenn ³ andn ⁴. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case. This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University.     

Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces

Let Σ be a collection of n algebraic surface patches in of constant maximum degree b, such that the boundary of each surface consists of a constant number of algebraic arcs, each of degree at most b as well. We show that the combinatorial complexity of the vertical decomposition of a single cell in the arrangement is O(n^{2+ɛ}), for any ɛ > 0, where the constant of proportionality depends on ɛ and on the maximum degree of the surfaces and of their boundaries. As an application, we obtain a near-quadratic motion-planning algorithm for general systems with three degrees of freedom. Received May 30, 1996, and in revised form February 18, 1997.     

On-line coloringk-colorable graphs

We show that for anyk, there exists an on-line algorithm that will color anyk-colorable graph onn vertices withO(n ^1−1/k! ) colors. This improves the previous best upper bound ofO(nlog^(2k−3) n/log^(2k−4) n) due to Lovász, Saks, and Trotter. In the special casesk=3 andk=4 we obtain on-line algorithms that useO(n ^2/3log^1/3 n) andO(n ^5/6log^1/6 n) colors, respectively.     

A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs

1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

On the number of minimal 1-Steiner trees

We count the number of nonisomorphic geometric minimum spanning trees formed by adding a single point to ann-point set ind-dimensional space, by relating it to a family of convex decompositions of space. TheO(n ^d log^{2d 2}−d n) bound that we obtain significantly improves previously known bounds and is tight to within a polylogarithmic factor. The research of D. Eppstein was performed in part while visiting Xerox PARC.     

Distributed algorithms solving the updating problems

In this paper, we consider the updating problems to reconstruct the biconnected-components and to reconstruct the weighted shortest path in response to the topology change of the network. We propose two distributed algorithms. The first algorithm solves the updating problem that reconstructs the biconnected-components after the several processors and links are added and deleted. Its bit complexity is O((n′ +a +d) logn′), its message complexity is O(n′ +a +d), the ideal time complexity isO(n′), and the space complexity isO(e logn +e′ logn′). The second algorithm solves the updating problem that reconstructs the weighted shortest path. Its message complexity and ideal-time complexity areO(u ² +a +n′) respectively.     

Visibility with One Reflection

We extend the concept of the polygon visible from a source point S in a simple polygon by considering visibility with two types of reflection, specular and diffuse. In specular reflection a light ray reflects from an edge of the polygon according to the rule: the angle of incidence equals the angle of reflection. In diffuse reflection a light ray reflects from an edge of the polygon in all inward directions. Several geometric and combinatorial properties of visibility polygons under these two types of reflection are described, when at most one reflection is permitted. We show that the visibility polygon Vs(S) under specular reflection may be nonsimple, while the visibility polygon Vd(S) under diffuse reflection is always simple. We present a Θ(n ² ) worst-case bound on the combinatorial complexity of both Vs(S) and Vd(S) and describe simple O(n ² log ² n) time algorithms for constructing the sets. Received September 27, 1995, and in revised form October 24, 1997.     

Polytopes in Arrangements

Consider an arrangement of n hyperplanes in \real ^d . 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 \real ³ we show an O(k ^1/3 n ² ) 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 \real ^d is Ω(k ^1/2 n ^d/2 ) which is a factor of away from the best known upper bound in the range n ^d-2 ≤ k ≤ n ^d . The case where 1≤ k ≤ n ^d-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.