共查询到20条相似文献,搜索用时 750 毫秒
1.
Given a fixed setS ofn points inE
3 and a query plane, the halfspace range search problem asks for the retrieval of all points ofS on a chosen side of. We prove that withO(n(logn)8 (loglogn)4) storage it is possible to solve this problem inO(k+logn) time, wherek is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the total number ofj-sets (j=1, ...,k) realized by a set ofn points inE
3 isO(nk
5); ak-set is any subset ofS of sizek which can be separated from the rest ofS by a plane.Supported in part by NSF grants MCS 83-03925 and the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146 and ARPA Order No. 4786.Supported in part by Joint Services Electronics Program under Contract N00014-79-C-0424. 相似文献
2.
Andrew V. Goldberg Michael D. Grigoriadis Robert E. Tarjan 《Mathematical Programming》1991,50(1-3):277-290
Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n
2
m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467. 相似文献
3.
The problem of selecting thekth largest or smallest element of {x
i
+y
j
|x
i
X andy
j
Y i,j} whereX=(x
1,x
2, ..,x
n
) andY=(y
1,y
2, ...,y
n
) are two arrays ofn elements each, is considered. Certain improvements to an existing algorithm are proposed. An algorithm requiringO(logk·logn) units of time on a Shared Memory Model of a parallel computer havingO(n
1+1/) processors is presented where is a pre-assigned constant lying between 1 and 2. 相似文献
4.
Polynomial dual network simplex algorithms 总被引:1,自引:0,他引:1
We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy leads to an O(m
2 logn) bound on the number of pivots, wheren andm denotes the number of nodes and arcs in the input network. If the demands are integral and at mostB, we also give an O(m(m+n logn) min(lognB, m logn))-time implementation of a strategy that requires somewhat more pivots.Research supported by AFOSR-88-0088 through the Air Force Office of Scientific Research, by NSF grant DOM-8921835 and by grants from Prime Computer Corporation and UPS.Research supported by NSF Research Initiation Award CCR-900-8226, by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by ONR Contract N00014-88-K-0166.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550. 相似文献
5.
W. Lenhart R. Pollack J. Sack R. Seidel M. Sharir S. Suri G. Toussaint S. Whitesides C. Yap 《Discrete and Computational Geometry》1988,3(1):281-293
The link center of a simple polygonP is the set of pointsx insideP at which the maximal link-distance fromx to any other point inP is minimized. Here the link distance between two pointsx, y insideP is defined to be the smallest number of straight edges in a polygonal path insideP connectingx toy. We prove several geometric properties of the link center and present an algorithm that calculates this set in timeO(n
2), wheren is the number of sides ofP. We also give anO(n logn) algorithm for finding an approximate link center, that is, a pointx such that the maximal link distance fromx to any point inP is at most one more than the value attained from the true link center.Work on this paper by the second author has been supported by National Science Foundation Grant DMS-8501947. Work by the third author has been supported by the Canadian National Science and Engineering Research Council, Grant A0332. Work by the fifth author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the seventh author has been supported by a Killam Senior Research Fellowship from the Canada Council, and work by the ninth author has been supported by the National Science Foundation Grants DCR-84-01898 and DCR-84-01633. Part of the work on this paper has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986. Further acknowledgments can be obtained from the tenth author upon request. 相似文献
6.
Jana Jurečková Pranab Kumar Sen 《Annals of the Institute of Statistical Mathematics》1990,42(2):345-357
For a general (real) parameter, let M
nbe the M-estimator and M
n
(1) be its one-step version (based on a suitable initial estimator M
n
(0)). It is known that, under certain regularity conditions, n(M
n
(1)-M
n)=O
p(1). The asymptotic distribution of n(M
n
(1)-M
n) is studied; it is typically non-normal and it reveals the role of the initial estimator M
n
(0).Work of this author was partially supported by the Office of Naval Research, Contract No. N00014-83-K-0387 相似文献
7.
Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x
1
x
2…x
r=y inG such thatx
1 ≺x
j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains
2
n
−o(n
2) relations. We prove that almost everyG
n,p satisfies this requirement if
, but almost noG
n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than
2
n
−δ(c)n
2 relations.
Partially supported by MCS Grant 8104854. 相似文献
8.
J. W. Daniel 《Journal of Optimization Theory and Applications》1973,12(3):233-241
In constrained optimization problems in mathematical programming, one wants to minimize a functionalf(x) over a given setC. If, at an approximate solutionx
n
, one replacesf(x) by its Taylor series expansion through quadratic terms atx
n
and denotes byx
n+1
the minimizing point for this overC, one has a direct analogue of Newton's method. The local convergence of this has been previously analyzed; here, we give global convergence results for this and the similar algorithm in which the constraint setC is also linearized at each step.This research was supported in part by the Office of Naval Research, Contract No. N00014-67-0126-0015, and was presented by invitation at the Fifth Gatlinburg Symposium on Numerical Algebra, Los Alamos, New Mexico, 1972. 相似文献
9.
The factor matroid of a graphG is the matric matroid of the vertex-edge incidence matrix ofG interpreted over the real numbers. This paper presents a constructive characterization of the graphs hat have the same factor matroid as a given 4-connected bipartite graph.Research partially supported by NSF Grant ESS-8307796 and Office of Naval Research Grant N00014-86-K-0689. 相似文献
10.
The edge-clique graphK(G) of a graphG is that graph whose vertices correspond to the edges ofG and where two vertices ofK(G) are adjacent whenever the corresponding edges ofG belong to a common clique. It is shown that every edge-clique graph is a clique graph, and that ifG is either an interval graph or a line graph, then so too isK(G). An algorithm is provided for determining whether a graph is an edge-clique graph. A new graph called the STP graph is introduced and a relationship involving this graph, the edge-clique graph, and the line graph is presented. The STP graphs are also characterized.Research supported in part by Office of Naval Research Contract N00014-88-K-0018.Research supported in part by Office of Naval Research Contract N00014-88-K-0163. 相似文献
11.
In this paper, we prove that there exists a schedule for routing any set of packets with edge-simple paths, on any network, inO(c+d) steps, wherec is the congestion of the paths in the network, andd is the length of the longest path. The result has applications to packet routing in parallel machines, network emulations, and job-shop scheduling.This research was conducted while the authors were at MIT. Support was provided by the Defense Advanced Research Projects Agency under Contract N00014-87-K-825, the Office of Naval Research under Contract N00014-86-K-0593, the Air Force under Contract OSR-86-0076, and the Army under Contract DAAL-03-86-K-0171. Tom Leighton is supported by an NSF Presidential Young Investigator Award with matching funds provided by IBM. 相似文献
12.
Pankaj K. Agarwal 《Discrete and Computational Geometry》1990,5(1):449-483
In this paper we consider the following problem: Given a set ofn lines in the plane, partition the plane intoO(r
2) triangles so that no triangle meets more thanO(n/r) lines of . We present a deterministic algorithm for this problem withO(nr logn/r) running time, where is a constant <3.33.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th Annual Symposium on Computational Geometry, 1989, pp. 11–22. 相似文献
13.
Michel Talagrand 《Israel Journal of Mathematics》1992,79(2-3):207-224
Consider a setA of symmetricn×n matricesa=(a
i,j)
i,j≤n
. Consider an independent sequence (g
i)
i≤n
of standard normal random variables, and letM=Esupa∈A|Σi,j⪯nai,jgigj|. Denote byN
2(A, α) (resp.N
t(A, α)) the smallest number of balls of radiusα for thel
2 norm ofR
n
2 (resp. the operator norm) needed to coverA. Then for a universal constantK we haveα(logN
2(A, α))1/4≤KM. This inequality is best possible. We also show that forδ≥0, there exists a constantK(δ) such thatα(logN
t≤K(δ)M.
Work partially supported by an N.S.F. grant. 相似文献
14.
In the present paper, we establish the stability and the superstability of a functional inequality corresponding to the functional equation fn(xyx) = ∑i+j+k=n fi(x)fj (y)fk(x). In addition, we take account of the problem of Jacobson radical ranges for such functional inequality. 相似文献
15.
We consider the problem of embedding a certain finite metric space to the Euclidean space, trying to keep the bi-Lipschitz
constant as small as possible. We introduce the notationc
2(X, d) for the least distortion with which the metric space (X, d) may be embedded in a Euclidean space. It is known that if (X, d) is a metric space withn points, thenc
2(X, d)≤0(logn) and the bound is tight. LetT be a tree withn vertices, andd be the metric induced by it. We show thatc
2(T, d)≤0(log logn), that is we provide an embeddingf of its vertices to the Euclidean space, such thatd(x, y)≤‖f(x)−f(y) ‖≤c log lognd(x, y) for some constantc.
Supported in part by grants from the Israeli Academy of Sciences and the US-Israel Binational Science Foundation.
Supported in part by NSF under grants CCR-9215293 and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New
Jersey Commission on Science and Technology. 相似文献
16.
Ravindra K. Ahuja Andrew V. Goldberg James B. Orlin Robert E. Tarjan 《Mathematical Programming》1992,53(1-3):243-266
Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm running in O(nm(log logU) log(nC)) time on networks withn vertices,m edges, maximum arc capacityU, and maximum arc cost magnitudeC. The major techniques used are the capacity-scaling approach of Edmonds and Karp, the excess-scaling approach of Ahuja and Orlin, the cost-scaling approach of Goldberg and Tarjan, and the dynamic tree data structure of Sleator and Tarjan. For nonsparse graphs with large maximum arc capacity, we obtain a similar but slightly better bound. We also obtain a slightly better bound for the (noncapacitated) transportation problem. In addition, we discuss a capacity-bounding approach to the minimum-cost flow problem.Research partially supported by an NSF Presidential Young Investigator Fellowship, Contract 8451517ECS, and grants from Analog Devices, Apple Computer Inc., and Prime Computer.On leave from Indian Institute of Technology, Kanpur, India.Research partially supported by an NSF Presidential Young Investigator Award.Research at Princeton University partially supported by National Science Foundation Grant DCR-8605962 and Office of Naval Research Contract N00014-87-K-0467. 相似文献
17.
LetF be a collection ofk-element sets with the property that the intersection of no two should be included in a third. We show that such a collection
of maximum size satisfies .2715k+o(k)≦≦log2 |F|≦.7549k+o(k) settling a question raised by Erdős. The lower bound is probabilistic, the upper bound is deduced via an entropy argument.
Some open questions are posed.
This research has been supported in part by the Office of Naval Research under Contract N00014-76-C-0366.
Supported in part by a NSF postdoctoral Fellowship. 相似文献
18.
Vernon Watts 《Probability Theory and Related Fields》1980,54(3):281-285
Summary Let {X
n} be independent and identically distributed and let X
kn
(n)
denote the k
n-th order statistic for X
1 ..., X
n, where k
n but k
n/n0. A representation for X
kn
(n)
in terms of the empirical distribution function is developed. The conditions include those under which X
kn
(n)
is asymptotically normal.Research partially supported by the University of North Carolina at Chapel Hill under Office of Naval Research Contract No. N00014-75-C-0809 and by The Florida State University under Office of Naval Research Contract No. N00014-76-C-0608. 相似文献
19.
This paper proposes algorithms for minimizing a continuously differentiable functionf(x):
n
subject to the constraint thatx does not lie in specified bounded subsets of
n
. Such problems arise in a variety of applications, such as tolerance design of electronic circuits and obstacle avoidance in the selection of trajectories for robot arms. Such constraints have the form
. The function is not continuously differentiable. Algorithms based on the use of generalized gradients have considerable disadvantages because of the local concavity of at points where the set {j|g
j
(x)=(x)} has more than one element. Algorithms which avoid these disadvantrages are presented, and their convergence is established.This research was sponsored in part by the National Science Foundation under Grant ECS-81-21149, the Air Force Office of Scientific Research (AFSC), United States Air Force under Contract F49620-79-C-0178, the Office of Naval Research under Grant N00014-83-K-0602, the Air Force Office of Scientific Research under Grant AFOSR-83-0361, and the Semiconductor Research Consortium under Grant SRC-82-11-008. 相似文献
20.
Let X be a normed space that satisfies the Johnson–Lindenstrauss lemma (J–L lemma, in short) in the sense that for any integer
n and any x
1,…,x
n
∈X, there exists a linear mapping L:X→F, where F⊆X is a linear subspace of dimension O(log n), such that ‖x
i
−x
j
‖≤‖L(x
i
)−L(x
j
)‖≤O(1)⋅‖x
i
−x
j
‖ for all i,j∈{1,…,n}. We show that this implies that X is almost Euclidean in the following sense: Every n-dimensional subspace of X embeds into Hilbert space with distortion
22O(log*n)2^{2^{O(\log^{*}n)}}
. On the other hand, we show that there exists a normed space Y which satisfies the J–L lemma, but for every n, there exists an n-dimensional subspace E
n
⊆Y whose Euclidean distortion is at least 2Ω(α(n)), where α is the inverse Ackermann function. 相似文献