---
_id: '4065'
abstract:
- lang: eng
text: We prove that given n⩾3 convex, compact, and pairwise disjoint sets in the
plane, they may be covered with n non-overlapping convex polygons with a total
of not more than 6n−9 sides, and with not more than 3n−6 distinct slopes. Furthermore,
we construct sets that require 6n−9 sides and 3n−6 slopes for n⩾3. The upper bound
on the number of slopes implies a new bound on a recently studied transversal
problem.
acknowledgement: 'The first author acknowledges the support by Amoco Fnd. Fat. Dev.
Comput. Sci. l-6-44862. Work on this paper by the second author was supported by
a Shell Fellowship in Computer Science. The third author as supported by the office
of Naval Research under grant NOOO14-86K-0416. '
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Arch
full_name: Robison, Arch
last_name: Robison
- first_name: Xiao
full_name: Shen, Xiao
last_name: Shen
citation:
ama: Edelsbrunner H, Robison A, Shen X. Covering convex sets with non-overlapping
polygons. Discrete Mathematics. 1990;81(2):153-164. doi:10.1016/0012-365X(90)90147-A
apa: Edelsbrunner, H., Robison, A., & Shen, X. (1990). Covering convex sets
with non-overlapping polygons. Discrete Mathematics. Elsevier. https://doi.org/10.1016/0012-365X(90)90147-A
chicago: Edelsbrunner, Herbert, Arch Robison, and Xiao Shen. “Covering Convex Sets
with Non-Overlapping Polygons.” Discrete Mathematics. Elsevier, 1990. https://doi.org/10.1016/0012-365X(90)90147-A.
ieee: H. Edelsbrunner, A. Robison, and X. Shen, “Covering convex sets with non-overlapping
polygons,” Discrete Mathematics, vol. 81, no. 2. Elsevier, pp. 153–164,
1990.
ista: Edelsbrunner H, Robison A, Shen X. 1990. Covering convex sets with non-overlapping
polygons. Discrete Mathematics. 81(2), 153–164.
mla: Edelsbrunner, Herbert, et al. “Covering Convex Sets with Non-Overlapping Polygons.”
Discrete Mathematics, vol. 81, no. 2, Elsevier, 1990, pp. 153–64, doi:10.1016/0012-365X(90)90147-A.
short: H. Edelsbrunner, A. Robison, X. Shen, Discrete Mathematics 81 (1990) 153–164.
date_created: 2018-12-11T12:06:44Z
date_published: 1990-04-15T00:00:00Z
date_updated: 2022-02-22T15:45:55Z
day: '15'
doi: 10.1016/0012-365X(90)90147-A
extern: '1'
intvolume: ' 81'
issue: '2'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0012365X9090147A?via%3Dihub
month: '04'
oa_version: None
page: 153 - 164
publication: Discrete Mathematics
publication_identifier:
eissn:
- 1872-681X
issn:
- 0012-365X
publication_status: published
publisher: Elsevier
publist_id: '2060'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Covering convex sets with non-overlapping polygons
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 81
year: '1990'
...
---
_id: '4074'
abstract:
- lang: eng
text: We present upper and lower bounds for extremal problems defined for arrangements
of lines, circles, spheres, and alike. For example, we prove that the maximum
number of edges boundingm cells in an arrangement ofn lines is Θ(m 2/3 n 2/3 +n),
and that it isO(m 2/3 n 2/3 β(n) +n) forn unit-circles, whereβ(n) (and laterβ(m,
n)) is a function that depends on the inverse of Ackermann's function and grows
extremely slowly. If we replace unit-circles by circles of arbitrary radii the
upper bound goes up toO(m 3/5 n 4/5 β(n) +n). The same bounds (without theβ(n)-terms)
hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees
in arrangements of lines and of unit-circles our bounds match previous results,
but our proofs are considerably simpler than the previous ones. The maximum sum
of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m
4/7 n 9/7 β(m, n) +n 2), in general, andO(m 3/4 n 3/4 β(m, n) +n) if no three
spheres intersect in a common circle. The latter bound implies that the maximum
number of unit-distances amongm points in three dimensions isO(m 3/2 β(m)) which
improves the best previous upper bound on this problem. Applications of our results
to other distance problems are also given.
acknowledgement: The research of the second author was supported by the National Science
Foundation under Grant CCR-8714565. Work by the fourth author has been supported
by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation
Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and
the IBM Corporation, and by a research grant from the NCRD, the Israeli National
Council for Research and Development. A preliminary version of this paper has appeared
in theProceedings of the 29th IEEE Symposium on Foundations of Computer Science,
1988.
article_processing_charge: No
article_type: original
author:
- first_name: Kenneth
full_name: Clarkson, Kenneth
last_name: Clarkson
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. Combinatorial complexity
bounds for arrangements of curves and spheres. Discrete & Computational
Geometry. 1990;5(1):99-160. doi:10.1007/BF02187783
apa: Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., & Welzl, E. (1990).
Combinatorial complexity bounds for arrangements of curves and spheres. Discrete
& Computational Geometry. Springer. https://doi.org/10.1007/BF02187783
chicago: Clarkson, Kenneth, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir,
and Emo Welzl. “Combinatorial Complexity Bounds for Arrangements of Curves and
Spheres.” Discrete & Computational Geometry. Springer, 1990. https://doi.org/10.1007/BF02187783.
ieee: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, “Combinatorial
complexity bounds for arrangements of curves and spheres,” Discrete & Computational
Geometry, vol. 5, no. 1. Springer, pp. 99–160, 1990.
ista: Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. 1990. Combinatorial
complexity bounds for arrangements of curves and spheres. Discrete & Computational
Geometry. 5(1), 99–160.
mla: Clarkson, Kenneth, et al. “Combinatorial Complexity Bounds for Arrangements
of Curves and Spheres.” Discrete & Computational Geometry, vol. 5,
no. 1, Springer, 1990, pp. 99–160, doi:10.1007/BF02187783.
short: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Discrete &
Computational Geometry 5 (1990) 99–160.
date_created: 2018-12-11T12:06:47Z
date_published: 1990-03-01T00:00:00Z
date_updated: 2022-02-17T15:41:04Z
day: '01'
doi: 10.1007/BF02187783
extern: '1'
intvolume: ' 5'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187783
month: '03'
oa_version: None
page: 99 - 160
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2048'
quality_controlled: '1'
status: public
title: Combinatorial complexity bounds for arrangements of curves and spheres
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...
---
_id: '4078'
abstract:
- lang: eng
text: In this paper we derived combinatorial point selection results for geometric
objects defined by pairs of points. In a nutshell, the results say that if many
pairs of a set of n points in some fixed dimension each define a geometric object
of some type, then there is a point covered by many of these objects. Based on
such a result for three-dimensional spheres we show that the combinatorial size
of the Delaunay triangulation of a point set in space can be reduced by adding
new points. We believe that from a practical point of view this is the most important
result of this paper.
article_processing_charge: No
author:
- first_name: Bernard
full_name: Chazelle, Bernard
last_name: Chazelle
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: John
full_name: Hershberger, John
last_name: Hershberger
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: 'Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. Slimming
down by adding; selecting heavily covered points. In: Proceedings of the 6th
Annual Symposium on Computational Geometry. ACM; 1990:116-127. doi:10.1145/98524.98551'
apa: 'Chazelle, B., Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., &
Sharir, M. (1990). Slimming down by adding; selecting heavily covered points.
In Proceedings of the 6th annual symposium on computational geometry (pp.
116–127). Berkley, CA, United States: ACM. https://doi.org/10.1145/98524.98551'
chicago: Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, John Hershberger,
Raimund Seidel, and Micha Sharir. “Slimming down by Adding; Selecting Heavily
Covered Points.” In Proceedings of the 6th Annual Symposium on Computational
Geometry, 116–27. ACM, 1990. https://doi.org/10.1145/98524.98551.
ieee: B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, and M.
Sharir, “Slimming down by adding; selecting heavily covered points,” in Proceedings
of the 6th annual symposium on computational geometry, Berkley, CA, United
States, 1990, pp. 116–127.
ista: 'Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M.
1990. Slimming down by adding; selecting heavily covered points. Proceedings of
the 6th annual symposium on computational geometry. SCG: Symposium on Computational
Geometry, 116–127.'
mla: Chazelle, Bernard, et al. “Slimming down by Adding; Selecting Heavily Covered
Points.” Proceedings of the 6th Annual Symposium on Computational Geometry,
ACM, 1990, pp. 116–27, doi:10.1145/98524.98551.
short: B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir,
in:, Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990,
pp. 116–127.
conference:
end_date: 1990-06-09
location: Berkley, CA, United States
name: 'SCG: Symposium on Computational Geometry'
start_date: 1990-06-07
date_created: 2018-12-11T12:06:48Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-17T10:09:54Z
day: '01'
doi: 10.1145/98524.98551
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/98524.98551
month: '01'
oa_version: None
page: 116 - 127
publication: Proceedings of the 6th annual symposium on computational geometry
publication_identifier:
isbn:
- 978-0-89791-362-1
publication_status: published
publisher: ACM
publist_id: '2046'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Slimming down by adding; selecting heavily covered points
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...
---
_id: '4076'
abstract:
- lang: eng
text: We present an algorithm to compute a Euclidean minimum spanning tree of a
given set S of n points in Ed in time O(Td(N, N) logd N), where Td(n, m) is the
time required to compute a bichromatic closest pair among n red and m blue points
in Ed. If Td(N, N) = Ω(N1+ε), for some fixed ε > 0, then the running time improves
to O(Td(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic
closets pair in expected time O((nm log n log m)2/3+m log2 n + n log2 m) in E3,
which yields an O(N4/3log4/3 N) expected time algorithm for computing a Euclidean
minimum spanning tree of N points in E3.
article_processing_charge: No
author:
- first_name: Pankaj
full_name: Agarwal, Pankaj
last_name: Agarwal
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Otfried
full_name: Schwarzkopf, Otfried
last_name: Schwarzkopf
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: 'Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. Euclidean minimum spanning
trees and bichromatic closest pairs. In: Proceedings of the 6th Annual Symposium
on Computational Geometry. ACM; 1990:203-210. doi:10.1145/98524.98567'
apa: 'Agarwal, P., Edelsbrunner, H., Schwarzkopf, O., & Welzl, E. (1990). Euclidean
minimum spanning trees and bichromatic closest pairs. In Proceedings of the
6th annual symposium on Computational geometry (pp. 203–210). Berkeley, CA,
United States: ACM. https://doi.org/10.1145/98524.98567'
chicago: Agarwal, Pankaj, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl.
“ Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” In Proceedings
of the 6th Annual Symposium on Computational Geometry, 203–10. ACM, 1990.
https://doi.org/10.1145/98524.98567.
ieee: P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, “ Euclidean minimum
spanning trees and bichromatic closest pairs,” in Proceedings of the 6th annual
symposium on Computational geometry, Berkeley, CA, United States, 1990, pp.
203–210.
ista: 'Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. 1990. Euclidean minimum
spanning trees and bichromatic closest pairs. Proceedings of the 6th annual symposium
on Computational geometry. SCG: Symposium on Computational Geometry, 203–210.'
mla: Agarwal, Pankaj, et al. “ Euclidean Minimum Spanning Trees and Bichromatic
Closest Pairs.” Proceedings of the 6th Annual Symposium on Computational Geometry,
ACM, 1990, pp. 203–10, doi:10.1145/98524.98567.
short: P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, in:, Proceedings of
the 6th Annual Symposium on Computational Geometry, ACM, 1990, pp. 203–210.
conference:
end_date: 1990-06-09
location: Berkeley, CA, United States
name: 'SCG: Symposium on Computational Geometry'
start_date: 1990-06-07
date_created: 2018-12-11T12:06:48Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-16T15:30:22Z
day: '01'
doi: 10.1145/98524.98567
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/98524.98567
month: '01'
oa_version: None
page: 203 - 210
publication: Proceedings of the 6th annual symposium on Computational geometry
publication_identifier:
isbn:
- 978-0-89791-362-1
publication_status: published
publisher: ACM
publist_id: '2044'
quality_controlled: '1'
scopus_import: '1'
status: public
title: ' Euclidean minimum spanning trees and bichromatic closest pairs'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...
---
_id: '4077'
abstract:
- lang: eng
text: We prove that for any set S of n points in the plane and n3-α triangles spanned
by the points of S there exists a point (not necessarily of S) contained in at
least n3-3α/(512 log25 n) of the triangles. This implies that any set of n points
in three - dimensional space defines at most 6.4n8/3 log5/3 n halving planes.
article_processing_charge: No
author:
- first_name: Boris
full_name: Aronov, Boris
last_name: Aronov
- first_name: Bernard
full_name: Chazelle, Bernard
last_name: Chazelle
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
- first_name: Rephael
full_name: Wenger, Rephael
last_name: Wenger
citation:
ama: 'Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. Points
and triangles in the plane and halving planes in space. In: Proceedings of
the 6th Annual Symposium on Computational Geometry. ACM; 1990:112-115. doi:10.1145/98524.98548'
apa: 'Aronov, B., Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., &
Wenger, R. (1990). Points and triangles in the plane and halving planes in space.
In Proceedings of the 6th annual symposium on Computational geometry (pp.
112–115). Berkley, CA, United States: ACM. https://doi.org/10.1145/98524.98548'
chicago: Aronov, Boris, Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas,
Micha Sharir, and Rephael Wenger. “Points and Triangles in the Plane and Halving
Planes in Space.” In Proceedings of the 6th Annual Symposium on Computational
Geometry, 112–15. ACM, 1990. https://doi.org/10.1145/98524.98548.
ieee: B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and R. Wenger,
“Points and triangles in the plane and halving planes in space,” in Proceedings
of the 6th annual symposium on Computational geometry, Berkley, CA, United
States, 1990, pp. 112–115.
ista: 'Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. 1990.
Points and triangles in the plane and halving planes in space. Proceedings of
the 6th annual symposium on Computational geometry. SCG: Symposium on Computational
Geometry, 112–115.'
mla: Aronov, Boris, et al. “Points and Triangles in the Plane and Halving Planes
in Space.” Proceedings of the 6th Annual Symposium on Computational Geometry,
ACM, 1990, pp. 112–15, doi:10.1145/98524.98548.
short: B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, R. Wenger,
in:, Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990,
pp. 112–115.
conference:
end_date: 1990-06-09
location: Berkley, CA, United States
name: 'SCG: Symposium on Computational Geometry'
start_date: 1990-06-07
date_created: 2018-12-11T12:06:48Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-17T09:42:27Z
day: '01'
doi: 10.1145/98524.98548
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/98524.98548
month: '01'
oa_version: None
page: 112 - 115
publication: Proceedings of the 6th annual symposium on Computational geometry
publication_identifier:
isbn:
- 978-0-89791-362-1
publication_status: published
publisher: ACM
publist_id: '2045'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Points and triangles in the plane and halving planes in space
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...