共查询到20条相似文献,搜索用时 31 毫秒
1.
Bernard Chazelle Herbert Edelsbrunner Leonidas Guibas Micha Sharir 《Discrete and Computational Geometry》1993,10(1):183-196
We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved
solutions for them. We obtain, for any fixed ε>0, anO(n
1+ε) algorithm for computing the diameter of a point set in 3-space, anO(8/5+ε) algorithm for computing the width of such a set, and onO(n
8/5+ε) algorithm for computing the closest pair in a set ofn lines in space. All these algorithms are deterministic.
Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352. Work by Herbert Edelsbrunner was supported by NSF Grant
CCR-89-21421. Work by Leonidas Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational Science Foundation.
Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the Fund
for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific
Research and Development. 相似文献
2.
Agarwal Pankaj K. Aronov Boris Pach János Pollack Richard Sharir Micha 《Combinatorica》1997,17(1):1-9
A graph is calledquasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph withn vertices isO(n).Work on this paper by Pankaj K. Agarwal, Boris Aronov and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work on this paper by Pankaj K. Agarwal has also been supported by NSF Grant CCR-93-01259, by an Army Research Office MURI grant DAAH04-96-1-0013, by an NYI award, and by matching funds from Xerox Corporation. Work on this paper by Boris Aronov has also been supported by NSF Grant CCR-92-11541 and by a Sloan Research Fellowship. Work on this paper by János Pach, Richard Pollack, and Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-94-24398. Work by János Pach was also supported by Grant OTKA-4269 and by a CUNY Research Award. Work by Richard Pollack was also supported by NSF Grants CCR-94-02640 and DMS-94-00293. Work by Micha Sharir was also supported by NSF Grant CCR-93-11127, by a Max-Planck Research Award, and by grants from the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Part of the work on this paper was done during the participation of the first four authors in the Special Semester on Computational and Combinatorial Geometry organized by the Mathematical Research Institute of Tel Aviv University, Spring 1995. 相似文献
3.
B. Chazelle H. Edelsbrunner M. Grigni L. Guibas M. Sharir E. Welzl 《Discrete and Computational Geometry》1995,13(1):1-15
LetS be a set ofn points in ℝ
d
. A setW is aweak ε-net for (convex ranges of)S if, for anyT⊆S containing εn points, the convex hull ofT intersectsW. We show the existence of weak ε-nets of size
, whereβ
2=0,β
3=1, andβ
d
≈0.149·2
d-1(d-1)!, improving a previous bound of Alonet al. Such a net can be computed effectively. We also consider two special cases: whenS is a planar point set in convex position, we prove the existence of a net of sizeO((1/ε) log1.6(1/ε)). In the case whereS consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of sizeO(1/ε), which improves a previous bound of Capoyleas.
Work by Bernard Chazelle has been supported by NSF Grant CCR-90-02352 and the Geometry Center. Work by Herbert Edelsbrunner
has been supported by NSF Grant CCR-89-21421. Work by Michelangelo Grigni has been supported by NSERC Operating Grants and
NSF Grant DMS-9206251. Work by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational
Science Foundation. Work by Emo Welzl and Micha Sharir has been supported by a grant from the G.I.F., the German-Israeli Foundation
for Scientific Research and Development. Work by Micha Sharir has also been supported by NSF Grant CCR-91-22103, and by a
grant from the Fund for Basic Research administered by the Israeli Academy of Sciences. 相似文献
4.
We consider the problem of planning the motion of an arbitraryk-sided polygonal robotB, free to translate and rotate in a polygonal environmentV bounded byn edges. We present an algorithm that constructs a single component of the free configuration space ofB in timeO((kn)
2+ɛ), for any ɛ>0. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying
motion-planning problem, within the same running time.
Work on this paper by Dan Halperin has been 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. Work on this paper
by Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-93-11127, by a Max-Planck Research Award, and by grants
from the U.S.-Israeli Binational Science Foundation, the Israel Science Fund administered by the Israeli Academy of Sciences,
and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. A preliminary and extended version
of the paper has appeared as: D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon
in a polygonal environment,Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 382–391. Part of the work on the paper was carried out while Dan Halperin was at Tel Aviv University. 相似文献
5.
We show that the number of topologically different orthographic views of a polyhedral terrain withn edges isO(n
5+ɛ
), and that the number of topologically different perspective views of such a terrain isO(n
8+ɛ
), for any ɛ>0. Both bounds are almost tight in the worst case. The proofs are simple consequences of the recent almost-tight
bounds of [11] on the complexity of lower envelopes in higher dimensions.
Pankaj Agarwal has been supported by National Science Foundation Grant CCR-91-06514. Micha Sharir has been supported by National
Science Foundation 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. 相似文献
6.
Boris Aronov Bernard Chazelle Herbert Edelsbrunner Leonidas J. Guibas Micha Sharir Rephael Wenger 《Discrete and Computational Geometry》1991,6(1):435-442
We prove that for any setS ofn points in the plane andn
3−α triangles spanned by the points inS there exists a point (not necessarily inS) contained in at leastn
3−3α/(c log5
n) of the triangles. This implies that any set ofn points in three-dimensional space defines at most
halving planes.
Work on this paper by Boris Aronov and Rephael Wenger has been supported by DIMACS under NSF Grant STC-88-09648. Work on this
paper by Bernard Chazelle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrunner has been supported by
NSF Grant CCR-87-14565. Micha Sharir has been supported by ONR Grant N00014-87-K-0129, by NSF Grant CCR-89-01484, and by grants
from the U.S.-Israeli Binational Science Foundation, the Israeli National Council for Research and Development, and the Fund
for Basic Research administered by the Israeli Academy of Sciences. 相似文献
7.
For eachd≥2, it is possible to placen points ind-space so that, given any two-coloring of the points, a half-space exists within which one color outnumbers the other by as
much ascn
1/2−1/2d
, for some constantc>0 depending ond. This result was proven in a slightly weaker form by Beck and the bound was later tightened by Alexander. It was recently
shown to be asymptotically optimal by Matoušek. We present a proof of the lower bound, which is based on Alexander's technique
but is technically simpler and more accessible. We present three variants of the proof, for three diffrent cases, to provide
more intuitive insight into the “large-discrepancy” phenomenon. We also give geometric and probabilistic interpretations of
the technique.
Work by Bernard Chazelle has been supported in part by NSF Grant CCR-90-02352 and The Geometry Center, University of Minnesota,
an STC funded by NSF, DOE, and Minnesota Technology, Inc. Work by Jiří Matoušek has been supported by Charles University Grant
No. 351, by Czech Republic Grant GAČR 201/93/2167 and in part by DIMACS. Work by Micha Sharir has been supported by NSF Grant
CCR-91-22103, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund
for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific
Research and Development. 相似文献
8.
Let G be a topological graph with n vertices, i.e., a graph drawn in the plane with edges drawn as simple Jordan curves. It is shown that, for any constants
k,l, there exists another constant C(k,l), such that if G has at least C(k,l)n edges, then it contains a k×l-gridlike configuration, that is, it contains k+l edges such that each of the first k edges crosses each of the last l edges. Moreover, one can require the first k edges to be incident to the same vertex.
Received: April, 2003
Janos Pach and Micha Sharir has been supported by NSF Grants CCR-97-32101 and CCR-00-98246, and by a joint grant from the
U.S.–Israel Binational Science Foundation. János Pach has also been supported by PSC-CUNY Research Award 63382-0032 and by
OTKA T-032452. Micha Sharir has also been supported by a grant from the Israeli Academy of Sciences for a Center of Excellence
in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University.
Géza Tóth has been supported by OTKA-T-038397 and by an award from the New York University Research Challenge Fund. 相似文献
9.
The overlay of 2≤m≤d minimization diagrams of n surfaces in ℝ
d
is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in ℝ
d+m−1. This elementary observation leads to a new bound on the complexity of the overlay of minimization diagrams of collections
of d-variate semi-algebraic surfaces, a tight bound on the complexity of the overlay of minimization diagrams of collections of
hyperplanes, and faster algorithms for constructing such overlays. Further algorithmic implications are discussed.
Work by V. Koltun was supported by NSF CAREER award CCF-0641402.
Work by M. Sharir was supported by NSF Grants CCR-00-98246 and CCF-05-14079, by a grant from the Israeli Academy of Sciences
for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski Minerva Center for
Geometry at Tel Aviv University. 相似文献
10.
We show that the total number of faces bounding any one cell in an arrangement ofn (d−1)-simplices in ℝ
d
isO(n
d−1 logn), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational
motion planning in polyhedral environments. We than extend our analysis to derive other results on complexity in arrangements
of simplices. For example, we show that in such an arrangement the total number of vertices incident to the same cell on more
than one “side” isO(n
d−1
logn). We, also show that the number of repetitions of a “k-flap,” formed by intersectingd−k given simplices, along the boundary of the same cell, summed over all cells and allk-flaps, isO(n
d−1
log2
n). We use this quantity, which we call theexcess of the arrangement, to derive bounds on the complexity ofm distinct cells of such an arrangement.
Work on this paper by the first author has been partially supported by National Science Foundation Grant CCR-92-11541. Work
on this paper by the second author has been supported by Office of Naval Research Grant N00014-90-J-1284, by National Science
Foundation Grants CCR-89-01484 and CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F.—the
German-Israeli Foundation for Scientific Reseach and Development, and the Fund for Basic Research administered by the Israeli
Academy of Sciences. 相似文献
11.
Marc van Kreveld Joseph S. B. Mitchell Peter Rousseeuw Micha Sharir Jack Snoeyink Bettina Speckmann 《Discrete and Computational Geometry》2008,39(4):656-677
We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n
d
) time and O(n
d−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog 2
n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric
and algorithmic results.
A preliminary version of this paper appeared in the proceedings of the 15th Annual ACM Symposium on Computational Geometry
(1999)
M. van Kreveld partially funded by the Netherlands Organization for Scientific Research (NWO) under FOCUS/BRICKS grant number
642.065.503.
J.S.B. Mitchell’s research largely conducted while the author was a Fulbright Research Scholar at Tel Aviv University. The
author is partially supported by NSF (CCR-9504192, CCR-9732220), Boeing, Bridgeport Machines, Sandia, Seagull Technology,
and Sun Microsystems.
M. Sharir supported by NSF Grants CCR-97-32101 and CCR-94-24398, 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 ESPRIT IV LTR project No. 21957
(CGAL), and by the Hermann Minkowski—MINERVA Center for Geometry at Tel Aviv University.
J. Snoeyink supported in part by grants from NSERC, the Killam Foundation, and CIES while at the University of British Columbia. 相似文献
12.
Let
be a collection of n compact convex sets in the plane such that the boundaries of any pair of sets in
intersect in at most s points for some constant s≥4. We show that the maximum number of regular vertices (intersection points of two boundaries that intersect twice) on the boundary of the union U of
is O
*(n
4/3), which improves earlier bounds due to Aronov et al. (Discrete Comput. Geom. 25, 203–220, 2001). The bound is nearly tight in the worst case. In this paper, a bound of the form O
*(f(n)) means that the actual bound is C
ε
f(n)⋅n
ε
for any ε>0, where C
ε
is a constant that depends on ε (and generally tends to ∞ as ε decreases to 0).
Work by János Pach and Micha Sharir was supported by NSF Grant CCF-05-14079, and by a grant from the U.S.–Israeli Binational
Science Foundation. Work by Esther Ezra and Micha Sharir was supported by grant 155/05 from the Israel Science Fund and by
the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Work on this paper by the first author has also
been supported by an IBM Doctoral Fellowship. A preliminary version of this paper has been presented in Proc. 23nd Annu. ACM Sympos. Comput. Geom., 2007, pp. 220–226.
E. Ezra’s current address: Department of Computer Science, Duke University, Durham, NC 27708-0129, USA. E-mail: esther@cs.duke.edu 相似文献
13.
We present several applications of a recent space-partitioning technique of Chazelle, Sharir, and Welzl (Proceedings of the 6th Annual ACM Symposium on Computational Geometry, 1990, pp. 23–33). Our results include efficient algorithms for output-sensitive hidden surface removal, for ray shooting in two and three dimensions, and for constructing spanning trees with low stabbing number.Work on this paper has been supported by DIMACS, an NSF Science and Technology Center, under Grant STC-88-09684. The second author has been supported by Office of Naval Research Grants N00014-89-J-3042 and N00014-90-J-1284, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. 相似文献
14.
It is shown that for every 1≤s≤n, the probability that thes-th largest eigenvalue of a random symmetricn-by-n matrix with independent random entries of absolute value at most 1 deviates from its median by more thant is at most 4e
−
t
232
s2. The main ingredient in the proof is Talagrand’s Inequality for concentration of measure in product spaces.
Research supported in part by a USA — Israel BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski
Minerva Center for Geometry at Tel Aviv University.
Research supported in part by a USA — Israel BSF grant and by a Bergmann Memorial Grant. 相似文献
15.
We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement ofn low-degree algebraic surface patches in 3-space. We show that this complexity isO(n
2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of
their boundaries. This extends several previous results, almost settles a 9-year-old open problem, and has applications to
motion planning of general robot systems with three degrees of freedom. As a corollary of the above result, we show that the
overall complexity of all the three-dimensional cells of an arrangement ofn low-degree algebraic surface patches, intersected by an additional low-degree algebraic surface patch σ (the so-calledzone of σ in the arrangement) isO(n
2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of
their boundaries.
Work on this paper by the first author has been 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. Work on this paper
by the second author has been supported by NSF Grants CCR-91-22103 and CCR-93-111327, 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
Israel Science Fund administered by the Israeli Academy of Sciences. 相似文献
16.
An upper bound for conforming Delaunay triangulations 总被引:1,自引:0,他引:1
A plane geometric graphC in ℝ2
conforms to another such graphG if each edge ofG is the union of some edges ofC. It is proved that, for everyG withn vertices andm edges, there is a completion of a Delaunay triangulation ofO(m
2
n) points that conforms toG. The algorithm that constructs the points is also described.
Research of the first author is supported by the National Science Foundation under Grant CCR-8921421 and under the Alan T.
Waterman award, Grant CCR-9118874. Any opinions, findings, and conclusions or recommendations expressed in this publication
are those of the authors and do not necessarily reflect the view of the National Science Foundation. Work of the second author
was conducted while he was on study leave at the University of Illinois. 相似文献
17.
Every collection oft≥2n
2 triangles with a total ofn vertices in ℝ3 has Ω(t
4/n
6) crossing pairs. This implies that one of their edges meets Ω(t
3/n
6) of the triangles. From this it follows thatn points in ℝ3 have onlyO(n
8/3) halving planes.
The research of H. Edelsbrunner was supported by the National Science Foundation under Grant CCR-8921421 and under an Alan
T. Waterman award, Grant CCR-9118874. Any opinions, findings and conclusions or recommendations expressed in this publication
are those of the authors and do not necessarily reflect the view of the National Science Foundation. 相似文献
18.
We discuss a technical problem arising in the motion planning algorithm of Kedem and Sharir [KS], and propose a way to overcome
it without increasing the asymptotic complexity of the algorithm
The first author was supported by the Eshkol Grant 04601-90 from the Israeli Ministry of Science and Technology. The second
author was partly supported by the Fund for Basic Research administered by the Israeli Academy of Sciences, by National Science
Foundation Grants CCR-91-22103 and CCR-93-11127, and by grants from the U.S.-Israeli Binational Science Foundation, and the
G.I.F., the German-Israeli Foundation for Scientific Research and Development. The third author was partly supported by the
Interdisciplinary Program at Tel-Aviv University. The third author’s current address is: Department of Computer Science, MIT,
Boston, MA, USA. 相似文献
19.
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
2
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. 相似文献
20.
Pankaj K. Agarwal Rolf Klein Christian Knauer Stefan Langerman Pat Morin Micha Sharir Michael Soss 《Discrete and Computational Geometry》2008,39(1-3):17-37
The detour and spanning ratio of a graph G embedded in
measure how well G approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe O(nlog n) time algorithms for computing the detour and spanning ratio of a planar polygonal path. By generalizing these algorithms,
we obtain O(nlog 2
n)-time algorithms for computing the detour or spanning ratio of planar trees and cycles. Finally, we develop subquadratic
algorithms for computing the detour and spanning ratio for paths, cycles, and trees embedded in
, and show that computing the detour in
is at least as hard as Hopcroft’s problem.
This research was partly funded by CRM, FCAR, MITACS, and NSERC. P.A. was supported by NSF under grants CCR-00-86013 EIA-99-72879,
EIA-01-31905, and CCR-02-04118, by ARO grants W911NF-04-1-0278 and DAAD19-03-1-0352, and by a grant from the U.S.-Israeli
Binational Science Foundation. R.K. was supported by DFG grant Kl 655/14-1. M.S. was supported by NSF Grants CCR-97-32101
and CCR-00-98246, by a grant from the U.S.-Israeli Binational Science Foundation (jointly with P.A.), by a grant from the
Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski–MINERVA
Center for Geometry at Tel Aviv University.
Some of these results have appeared in a preliminary form in [2, 20]. 相似文献