共查询到20条相似文献,搜索用时 46 毫秒
1.
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. 相似文献
2.
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. 相似文献
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.
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. 相似文献
5.
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. 相似文献
6.
Let P be a set of n points in ℝ
d
. A subset
of P is called a (k,ε)-kernel if for every direction, the directional width of
ε-approximates that of P, when k “outliers” can be ignored in that direction. We show that a (k,ε)-kernel of P of size O(k/ε
(d−1)/2) can be computed in time O(n+k
2/ε
d−1). The new algorithm works by repeatedly “peeling” away (0,ε)-kernels from the point set.
We also present a simple ε-approximation algorithm for fitting various shapes through a set of points with at most k outliers. The algorithm is incremental and works by repeatedly “grating” critical points into a working set, till the working
set provides the required approximation. We prove that the size of the working set is independent of n, and thus results in a simple and practical, near-linear ε-approximation algorithm for shape fitting with outliers in low dimensions.
We demonstrate the practicality of our algorithms by showing their empirical performance on various inputs and problems.
A preliminary version of this paper appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 182–191. P.A. and H.Y. are supported by NSF under grants CCR-00-86013, EIA-01-31905, CCR-02-04118, and DEB-04-25465,
by ARO grants W911NF-04-1-0278 and DAAD19-03-1-0352, and by a grant from the U.S.–Israel Binational Science Foundation. S.H.-P.
is supported by a NSF CAREER award CCR-0132901. 相似文献
7.
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. 相似文献
8.
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. 相似文献
9.
Given disjoint setsP
1,P
2, ...,P
d
inR
d
withn points in total, ahamsandwich cut is a hyperplane that simultaneously bisects theP
i
. We present algorithms for finding ham-sandwich cuts in every dimensiond>1. Whend=2, the algorithm is optimal, having complexityO(n). For dimensiond>2, the bound on the running time is proportional to the worst-case time needed for constructing a level in an arrangement
ofn hyperplanes in dimensiond−1. This, in turn, is related to the number ofk-sets inR
d−1
. With the current estimates, we get complexity close toO(n
3/2
) ford=3, roughlyO(n
8/3
) ford=4, andO(n
d−1−a(d)
) for somea(d)>0 (going to zero asd increases) for largerd. We also give a linear-time algorithm for ham-sandwich cuts inR
3 when the three sets are suitably separated.
A preliminary version of the results of this paper appeared in [16] and [17]. Part of this research by J. Matoušek was done
while he was visiting the School of Mathematics, Georgia Institute of Technology, Atlanta, and part of his work on this paper
was supported by a Humboldt Research Fellowship. W. Steiger expresses gratitude to the NSF DIMACS Center at Rutgers, and his
research was supported in part by NSF Grants CCR-8902522 and CCR-9111491. 相似文献
10.
L. J. Guibas D. Halperin J. Matoušek M. Sharir 《Discrete and Computational Geometry》1995,14(1):113-122
We show that, for any collection ℋ ofn hyperplanes in ℜ4, the combinatorial complexity of thevertical decomposition of the arrangementA(ℋ) of ℋ isO(n
4 logn). The proof relies on properties of superimposed convex subdivisions of 3-space, and we also derive some other results concerning
them.
Work on this paper by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science
Foundation. Work by Leonidas Guibas was also supported by National Science Foundation Grant CCR-9215219. Work by Micha Sharir
was also supported by National Science Foundation Grant CCR-91-22103, and by grants from the G.I.F.—the German Isreali Foundation
for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.
Work by Jiří Matouŝek was done while he was visiting Tel Aviv University, and its was partially supported by a Humboldt Research
Fellowship. Work on this paper by Dan Halperin was carried out while he was at Tel Aviv University. 相似文献
11.
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. 相似文献
12.
Given a setS ofn points inR
d
, a subsetX of sized is called ak-simplex if the hyperplane aff(X) has exactlyk points on one side. We studyE
d
(k,n), the expected number of k-simplices whenS is a random sample ofn points from a probability distributionP onR
d
. WhenP is spherically symmetric we prove thatE
d
(k, n)≤cn
d−1 WhenP is uniform on a convex bodyK⊂R
2 we prove thatE
2
(k, n) is asymptotically linear in the rangecn≤k≤n/2 and whenk is constant it is asymptotically the expected number of vertices on the convex hull ofS. Finally, we construct a distributionP onR
2 for whichE
2((n−2)/2,n) iscn logn.
The authors express gratitude to the NSF DIMACS Center at Rutgers and Princeton. The research of I. Bárány was supported in
part by Hungarian National Science Foundation Grants 1907 and 1909, and W. Steiger's research was supported in part by NSF
Grants CCR-8902522 and CCR-9111491. 相似文献
13.
Pankaj K. Agarwal Herbert Edelsbrunner Otfried Schwarzkopf Emo Welzl 《Discrete and Computational Geometry》1991,6(1):407-422
We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE
d
in timeO(F
d
(N,N) log
d
N), whereF
d
(n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE
d
. IfF
d
(N,N)=Ω(N
1+ε), for some fixed ɛ>0, then the running time improves toO(F
d
(N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)2/3+m log2
n+n log2
m) inE
3, which yields anO(N
4/3 log4/3
N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE
3. Ind≥4 dimensions we obtain expected timeO((nm)1−1/([d/2]+1)+ε+m logn+n logm) for the bichromatic closest pair problem andO(N
2−2/([d/2]+1)ε) for the Euclidean minimum spanning tree problem, for any positive ɛ.
The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer
Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's
work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the
Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”.
The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No.
3075 (project ALCOM). 相似文献
14.
In 1995, Roper and Suffridge defined an extension operator which maps a locally biholomorphic function on the unit diskD in ℂ to a locally biholomorphic mapping on the unit ballB
n in ℂn. This extension operator preserves many important properties, e.g., convexity and starlikeness, etc. In this note, we introduce
the family ofε starlike mappings, and prove that the Roper-Suffridge extension operator preserves theε starlikeness on some Reinhardt domains. This result includes many known results and solves an open problem of Graham and
Kohr.
Project supported by the National Science Foundation of China. 相似文献
15.
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. 相似文献
16.
In this paper we consider generalized convexity and concavity properties of the optimal value functionf
* for the general parametric optimization problemP(ε) of the form min
x
f(x, ε) s.t.x∈R(ε). Many results on convexity and concavity characterizations off
* were presented by the authors in a previous paper. Such properties off
* and the solution set mapS
* form an important part of the theoretical basis for sensitivity, stability and parametric analysis in mathematical optimization.
We give sufficient conditions for several types of generalized convexity and concavity off
*, in terms of respective generalized convexity and concavity assumptions onf and convexity and concavity assumptions on the feasible region point-to-set mapR. Specializations of these results to the parametric inequality-equality constrained nonlinear programming problem are provided.
Research supported by Grant ECS-8619859, National Science Foundation and Contract N00014-86-K-0052, Office of Naval Research. 相似文献
17.
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. 相似文献
18.
M. T. Goodrich 《Discrete and Computational Geometry》1995,14(1):445-462
We given anO(n logn)-time method for finding a bestk-link piecewise-linear function approximating ann-point planar point set using the well-known uniform metric to measure the error, ε≥0, of the approximation. Our methods is
based upon new characterizations of such functions, which we exploit to design an efficient algorithm using a plane sweep
in “ε space” followed by several applications of the parametric-searching technique. The previous best running time for this
problems wasO(n
2).
This research was announced in preliminary form at the 10th ACM Symposium on Computational Geometry. The author was partially
supported by the NSF and DARPA under Grant CCR-8908092, and by the NSF under Grants IRI-9116843 and CCR-9300079. 相似文献
19.
Robert S. Strichartz 《Journal d'Analyse Mathématique》2006,99(1):333-353
For certain Cantor measures μ on ℝn, it was shown by Jorgensen and Pedersen that there exists an orthonormal basis of exponentialse
2πiγ·x for λεΛ. a discrete subset of ℝn called aspectrum for μ. For anyL
1 functionf, we define coefficientsc
γ(f)=∝f(y)e
−2πiγiy
dμ(y) and form the Mock Fourier series ∑λ∈Λcλ(f)e
2πiλ·x
. There is a natural sequence of finite subsets Λn increasing to Λ asn→∞, and we define the partial sums of the Mock Fourier series by
We prove, under mild technical assumptions on μ and Λ, thats
n(f) converges uniformly tof for any continuous functionf and obtain the rate of convergence in terms of the modulus of continuity off. We also show, under somewhat stronger hypotheses, almost everywhere convergence forfεL
1.
Research supported in part by the National Science Foundation, Grant DMS-0140194. 相似文献
20.
Nariankadu D. Shyamalkumar Kasturi Varadarajan 《Discrete and Computational Geometry》2012,47(1):44-63
We consider the problem of fitting a subspace of a specified dimension k to a set P of n points in ℝ
d
. The fit of a subspace F is measured by the L
τ
norm, that is, it is defined as the τ-root of the sum of the τth powers of the Euclidean distances of the points in P from F, for some τ≥1. Our main result is a randomized algorithm that takes as input P, k, and a parameter 0<ε<1; runs in
nd ·2O(\fractk2e log2 \frac ke)nd \cdot2^{O(\frac{\tau k^{2}}{\varepsilon} \log^{2} \frac {k}{\varepsilon})} time, and returns a k-subspace that with probability at least 1/2 has a fit that is at most (1+ε) times that of the optimal k-subspace. 相似文献