[{"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."}],"oa_version":"None","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0012365X9090147A?via%3Dihub"}],"scopus_import":"1","intvolume":" 81","month":"04","publication_status":"published","publication_identifier":{"eissn":["1872-681X"],"issn":["0012-365X"]},"language":[{"iso":"eng"}],"issue":"2","volume":81,"_id":"4065","type":"journal_article","article_type":"original","status":"public","date_updated":"2022-02-22T15:45:55Z","extern":"1","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. ","publisher":"Elsevier","quality_controlled":"1","year":"1990","publication":"Discrete Mathematics","day":"15","page":"153 - 164","date_created":"2018-12-11T12:06:44Z","date_published":"1990-04-15T00:00:00Z","doi":"10.1016/0012-365X(90)90147-A","citation":{"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.","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.","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.","short":"H. Edelsbrunner, A. Robison, X. Shen, Discrete Mathematics 81 (1990) 153–164.","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","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"},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","article_processing_charge":"No","author":[{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert"},{"full_name":"Robison, Arch","last_name":"Robison","first_name":"Arch"},{"last_name":"Shen","full_name":"Shen, Xiao","first_name":"Xiao"}],"publist_id":"2060","title":"Covering convex sets with non-overlapping polygons"},{"article_processing_charge":"No","publist_id":"2048","author":[{"first_name":"Kenneth","full_name":"Clarkson, Kenneth","last_name":"Clarkson"},{"first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"last_name":"Sharir","full_name":"Sharir, Micha","first_name":"Micha"},{"first_name":"Emo","full_name":"Welzl, Emo","last_name":"Welzl"}],"title":"Combinatorial complexity bounds for arrangements of curves and spheres","citation":{"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.","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.","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.","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","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"},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publisher":"Springer","quality_controlled":"1","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.","page":"99 - 160","date_created":"2018-12-11T12:06:47Z","date_published":"1990-03-01T00:00:00Z","doi":"10.1007/BF02187783","year":"1990","publication":"Discrete & Computational Geometry","day":"01","article_type":"original","type":"journal_article","status":"public","_id":"4074","date_updated":"2022-02-17T15:41:04Z","extern":"1","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187783"}],"intvolume":" 5","month":"03","abstract":[{"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.","lang":"eng"}],"oa_version":"None","volume":5,"issue":"1","publication_status":"published","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"language":[{"iso":"eng"}]},{"citation":{"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.","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.","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.","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","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","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."},"date_updated":"2022-02-17T10:09:54Z","extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publist_id":"2046","author":[{"last_name":"Chazelle","full_name":"Chazelle, Bernard","first_name":"Bernard"},{"last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"first_name":"John","last_name":"Hershberger","full_name":"Hershberger, John"},{"first_name":"Raimund","full_name":"Seidel, Raimund","last_name":"Seidel"},{"last_name":"Sharir","full_name":"Sharir, Micha","first_name":"Micha"}],"article_processing_charge":"No","title":"Slimming down by adding; selecting heavily covered points","_id":"4078","type":"conference","conference":{"start_date":"1990-06-07","location":"Berkley, CA, United States","end_date":"1990-06-09","name":"SCG: Symposium on Computational Geometry"},"status":"public","publication_identifier":{"isbn":["978-0-89791-362-1"]},"year":"1990","publication_status":"published","day":"01","language":[{"iso":"eng"}],"publication":"Proceedings of the 6th annual symposium on computational geometry","page":"116 - 127","doi":"10.1145/98524.98551","date_published":"1990-01-01T00:00:00Z","date_created":"2018-12-11T12:06:48Z","abstract":[{"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.","lang":"eng"}],"oa_version":"None","publisher":"ACM","quality_controlled":"1","scopus_import":"1","main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/98524.98551"}],"month":"01"},{"abstract":[{"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.","lang":"eng"}],"oa_version":"None","publisher":"ACM","scopus_import":"1","quality_controlled":"1","main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/98524.98567"}],"month":"01","publication_identifier":{"isbn":["978-0-89791-362-1"]},"publication_status":"published","year":"1990","day":"01","publication":"Proceedings of the 6th annual symposium on Computational geometry","language":[{"iso":"eng"}],"page":"203 - 210","date_published":"1990-01-01T00:00:00Z","doi":"10.1145/98524.98567","date_created":"2018-12-11T12:06:48Z","_id":"4076","type":"conference","conference":{"location":"Berkeley, CA, United States","end_date":"1990-06-09","start_date":"1990-06-07","name":"SCG: Symposium on Computational Geometry"},"status":"public","date_updated":"2022-02-16T15:30:22Z","citation":{"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.","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.","short":"P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, in:, Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990, pp. 203–210.","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.","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."},"extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publist_id":"2044","author":[{"last_name":"Agarwal","full_name":"Agarwal, Pankaj","first_name":"Pankaj"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"},{"last_name":"Schwarzkopf","full_name":"Schwarzkopf, Otfried","first_name":"Otfried"},{"last_name":"Welzl","full_name":"Welzl, Emo","first_name":"Emo"}],"article_processing_charge":"No","title":" Euclidean minimum spanning trees and bichromatic closest pairs"},{"month":"01","main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/98524.98548"}],"quality_controlled":"1","scopus_import":"1","publisher":"ACM","oa_version":"None","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."}],"date_created":"2018-12-11T12:06:48Z","date_published":"1990-01-01T00:00:00Z","doi":"10.1145/98524.98548","page":"112 - 115","language":[{"iso":"eng"}],"publication":"Proceedings of the 6th annual symposium on Computational geometry","day":"01","year":"1990","publication_status":"published","publication_identifier":{"isbn":["978-0-89791-362-1"]},"status":"public","conference":{"name":"SCG: Symposium on Computational Geometry","start_date":"1990-06-07","end_date":"1990-06-09","location":"Berkley, CA, United States"},"type":"conference","_id":"4077","title":"Points and triangles in the plane and halving planes in space","article_processing_charge":"No","author":[{"first_name":"Boris","last_name":"Aronov","full_name":"Aronov, Boris"},{"full_name":"Chazelle, Bernard","last_name":"Chazelle","first_name":"Bernard"},{"first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner"},{"last_name":"Guibas","full_name":"Guibas, Leonidas","first_name":"Leonidas"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"},{"first_name":"Rephael","full_name":"Wenger, Rephael","last_name":"Wenger"}],"publist_id":"2045","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","date_updated":"2022-02-17T09:42:27Z","citation":{"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.","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.","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","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.","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.","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."}}]