[{"publication":"Discrete & Computational Geometry","month":"01","oa_version":"None","language":[{"iso":"eng"}],"type":"journal_article","date_published":"2001-01-01T00:00:00Z","publist_id":"4506","publication_identifier":{"issn":["0179-5376"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","issue":"2","author":[{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}],"scopus_import":"1","_id":"2419","intvolume":"        26","title":"A continuous analogue of the Upper Bound Theorem","article_processing_charge":"No","date_created":"2018-12-11T11:57:33Z","publication_status":"published","quality_controlled":"1","page":"205 - 219","article_type":"original","publisher":"Springer","year":"2001","citation":{"short":"U. Wagner, E. Welzl, Discrete &#38; Computational Geometry 26 (2001) 205–219.","mla":"Wagner, Uli, and Emo Welzl. “A Continuous Analogue of the Upper Bound Theorem.” <i>Discrete &#38; Computational Geometry</i>, vol. 26, no. 2, Springer, 2001, pp. 205–19, doi:<a href=\"https://doi.org/10.1007/s00454-001-0028-9\">10.1007/s00454-001-0028-9</a>.","ista":"Wagner U, Welzl E. 2001. A continuous analogue of the Upper Bound Theorem. Discrete &#38; Computational Geometry. 26(2), 205–219.","apa":"Wagner, U., &#38; Welzl, E. (2001). A continuous analogue of the Upper Bound Theorem. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-001-0028-9\">https://doi.org/10.1007/s00454-001-0028-9</a>","ama":"Wagner U, Welzl E. A continuous analogue of the Upper Bound Theorem. <i>Discrete &#38; Computational Geometry</i>. 2001;26(2):205-219. doi:<a href=\"https://doi.org/10.1007/s00454-001-0028-9\">10.1007/s00454-001-0028-9</a>","chicago":"Wagner, Uli, and Emo Welzl. “A Continuous Analogue of the Upper Bound Theorem.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2001. <a href=\"https://doi.org/10.1007/s00454-001-0028-9\">https://doi.org/10.1007/s00454-001-0028-9</a>.","ieee":"U. Wagner and E. Welzl, “A continuous analogue of the Upper Bound Theorem,” <i>Discrete &#38; Computational Geometry</i>, vol. 26, no. 2. Springer, pp. 205–219, 2001."},"date_updated":"2023-05-24T13:13:51Z","abstract":[{"lang":"eng","text":"For an absolutely continuous probability measure μ. on ℝd and a nonnegative integer k, let S̃k(μ, 0) denote the probability that the convex hull of k + d + 1 random points which are i.i.d. according to μ contains the origin 0. For d and k given, we determine a tight upper bound on S̃k(μ, 0), and we characterize the measures in ℝd which attain this bound. As we will see, this result can be considered a continuous analogue of the Upper Bound Theorem for the maximal number of faces of convex polytopes with a given number of vertices. For our proof we introduce so-called h-functions, continuous counterparts of h-vectors of simplicial convex polytopes."}],"day":"01","doi":"10.1007/s00454-001-0028-9","extern":"1","acknowledgement":"We are indebted to Rolf Schneider for many helpful remarks and in particular for bringing reference [6] to our attention","volume":26},{"language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","month":"04","oa_version":"None","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","date_published":"2001-04-04T00:00:00Z","type":"journal_article","publist_id":"2122","publication_identifier":{"issn":["0179-5376"]},"page":"525 - 568","quality_controlled":"1","article_type":"original","publisher":"Springer","author":[{"full_name":"Cheng, Ho","last_name":"Cheng","first_name":"Ho"},{"first_name":"Tamal","last_name":"Dey","full_name":"Dey, Tamal"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"full_name":"Sullivan, John","first_name":"John","last_name":"Sullivan"}],"issue":"4","_id":"4007","scopus_import":"1","title":"Dynamic skin triangulation","intvolume":"        25","publication_status":"published","date_created":"2018-12-11T12:06:24Z","article_processing_charge":"No","extern":"1","volume":25,"acknowledgement":"NSF under grant DMS- 98-73945, ARO under grant DAAG55-98-1-0177, NSF under grants CCR-96- 19542 and CCR-97-12088.","date_updated":"2023-05-10T12:45:59Z","year":"2001","citation":{"ieee":"H. Cheng, T. Dey, H. Edelsbrunner, and J. Sullivan, “Dynamic skin triangulation,” <i>Discrete &#38; Computational Geometry</i>, vol. 25, no. 4. Springer, pp. 525–568, 2001.","chicago":"Cheng, Ho, Tamal Dey, Herbert Edelsbrunner, and John Sullivan. “Dynamic Skin Triangulation.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2001. <a href=\"https://doi.org/10.1007/s00454-001-0007-1\">https://doi.org/10.1007/s00454-001-0007-1</a>.","ama":"Cheng H, Dey T, Edelsbrunner H, Sullivan J. Dynamic skin triangulation. <i>Discrete &#38; Computational Geometry</i>. 2001;25(4):525-568. doi:<a href=\"https://doi.org/10.1007/s00454-001-0007-1\">10.1007/s00454-001-0007-1</a>","apa":"Cheng, H., Dey, T., Edelsbrunner, H., &#38; Sullivan, J. (2001). Dynamic skin triangulation. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-001-0007-1\">https://doi.org/10.1007/s00454-001-0007-1</a>","ista":"Cheng H, Dey T, Edelsbrunner H, Sullivan J. 2001. Dynamic skin triangulation. Discrete &#38; Computational Geometry. 25(4), 525–568.","mla":"Cheng, Ho, et al. “Dynamic Skin Triangulation.” <i>Discrete &#38; Computational Geometry</i>, vol. 25, no. 4, Springer, 2001, pp. 525–68, doi:<a href=\"https://doi.org/10.1007/s00454-001-0007-1\">10.1007/s00454-001-0007-1</a>.","short":"H. Cheng, T. Dey, H. Edelsbrunner, J. Sullivan, Discrete &#38; Computational Geometry 25 (2001) 525–568."},"abstract":[{"text":"This paper describes an algorithm for maintaining an approximating triangulation of a deforming surface in R 3 . The surface is the envelope of an infinite family of spheres defined and controlled by a finite collection of weighted points. The triangulation adapts dynamically to changing shape, curvature, and topology of the surface. ","lang":"eng"}],"doi":"10.1007/s00454-001-0007-1","day":"04"},{"publist_id":"2119","publication_identifier":{"issn":["0179-5376"]},"date_published":"2000-12-01T00:00:00Z","type":"journal_article","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","month":"12","oa_version":"None","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}],"abstract":[{"text":"In this paper we introduce the abacus model of a simplex and use it to subdivide a d-simplex into k(d) d-simplices all of the same volume and shape characteristics. The construction is an extension of the subdivision method of Freudenthal [3] and has been used by Goodman and Peters [4] to design smooth manifolds.","lang":"eng"}],"doi":"10.1007/s004540010063","day":"01","date_updated":"2023-05-02T11:43:59Z","year":"2000","citation":{"mla":"Edelsbrunner, Herbert, and Daniel Grayson. “Edgewise Subdivision of a Simplex.” <i>Discrete &#38; Computational Geometry</i>, vol. 24, no. 4, Springer, 2000, pp. 707–19, doi:<a href=\"https://doi.org/10.1007/s004540010063\">10.1007/s004540010063</a>.","short":"H. Edelsbrunner, D. Grayson, Discrete &#38; Computational Geometry 24 (2000) 707–719.","ista":"Edelsbrunner H, Grayson D. 2000. Edgewise subdivision of a simplex. Discrete &#38; Computational Geometry. 24(4), 707–719.","ama":"Edelsbrunner H, Grayson D. Edgewise subdivision of a simplex. <i>Discrete &#38; Computational Geometry</i>. 2000;24(4):707-719. doi:<a href=\"https://doi.org/10.1007/s004540010063\">10.1007/s004540010063</a>","apa":"Edelsbrunner, H., &#38; Grayson, D. (2000). Edgewise subdivision of a simplex. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s004540010063\">https://doi.org/10.1007/s004540010063</a>","ieee":"H. Edelsbrunner and D. Grayson, “Edgewise subdivision of a simplex,” <i>Discrete &#38; Computational Geometry</i>, vol. 24, no. 4. Springer, pp. 707–719, 2000.","chicago":"Edelsbrunner, Herbert, and Daniel Grayson. “Edgewise Subdivision of a Simplex.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2000. <a href=\"https://doi.org/10.1007/s004540010063\">https://doi.org/10.1007/s004540010063</a>."},"extern":"1","volume":24,"acknowledgement":"NSF under Grant DMS 98-73945, NSF under Grant CCR-96-19542 and by ARO under Grant DAAG55- 98-1-0177.","title":"Edgewise subdivision of a simplex","intvolume":"        24","publication_status":"published","date_created":"2018-12-11T12:06:23Z","article_processing_charge":"No","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner"},{"full_name":"Grayson, Daniel","last_name":"Grayson","first_name":"Daniel"}],"issue":"4","_id":"4004","scopus_import":"1","article_type":"original","publisher":"Springer","page":"707 - 719","quality_controlled":"1"},{"date_published":"1999-01-01T00:00:00Z","type":"journal_article","publist_id":"2115","publication_identifier":{"issn":["0179-5376"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","publication":"Discrete & Computational Geometry","month":"01","oa_version":"None","language":[{"iso":"eng"}],"date_updated":"2022-09-06T09:02:23Z","year":"1999","citation":{"apa":"Edelsbrunner, H. (1999). Deformable smooth surface design. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/PL00009412\">https://doi.org/10.1007/PL00009412</a>","ama":"Edelsbrunner H. Deformable smooth surface design. <i>Discrete &#38; Computational Geometry</i>. 1999;21(1):87-115. doi:<a href=\"https://doi.org/10.1007/PL00009412\">10.1007/PL00009412</a>","ieee":"H. Edelsbrunner, “Deformable smooth surface design,” <i>Discrete &#38; Computational Geometry</i>, vol. 21, no. 1. Springer, pp. 87–115, 1999.","chicago":"Edelsbrunner, Herbert. “Deformable Smooth Surface Design.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1999. <a href=\"https://doi.org/10.1007/PL00009412\">https://doi.org/10.1007/PL00009412</a>.","short":"H. Edelsbrunner, Discrete &#38; Computational Geometry 21 (1999) 87–115.","mla":"Edelsbrunner, Herbert. “Deformable Smooth Surface Design.” <i>Discrete &#38; Computational Geometry</i>, vol. 21, no. 1, Springer, 1999, pp. 87–115, doi:<a href=\"https://doi.org/10.1007/PL00009412\">10.1007/PL00009412</a>.","ista":"Edelsbrunner H. 1999. Deformable smooth surface design. Discrete &#38; Computational Geometry. 21(1), 87–115."},"abstract":[{"text":"A new paradigm for designing smooth surfaces is described. A finite set of points with weights specifies a closed surface in space referred to as skin. It consists of one or more components, each tangent continuous and free of self-intersections and intersections with other components. The skin varies continuously with the weights and locations of the points, and the variation includes the possibility of a topology change facilitated by the violation of tangent continuity at a single point in space and time. Applications of the skin to molecular modeling and to geometric deformation are discussed.","lang":"eng"}],"doi":"10.1007/PL00009412","day":"01","extern":"1","volume":21,"author":[{"last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"issue":"1","_id":"4014","scopus_import":"1","title":"Deformable smooth surface design","intvolume":"        21","publication_status":"published","date_created":"2018-12-11T12:06:26Z","article_processing_charge":"No","page":"87 - 115","quality_controlled":"1","article_type":"original","publisher":"Springer"},{"extern":"1","volume":17,"acknowledgement":"Partially supported by the National Science Foundation, under Grant ASC-9200301 and the Alan T. Waterman award, Grant CCR-9118874.","abstract":[{"text":"A halving hyperplane of a set S of n points in R(d) contains d affinely independent points of S so that equally many of the points off the hyperplane lie in each of the two half-spaces. We prove bounds on the number of halving hyperplanes under the condition that the ratio of largest over smallest distance between any two points is at most delta n(1/d), delta some constant. Such a set S is called dense. In d = 2 dimensions the number of halving lines for a dense set can be as much as Omega(n log n), and it cannot exceed O (n(5/4)/log* n). The upper bound improves over the current best bound of O (n(3/2)/log* n) which holds more generally without any density assumption. In d = 3 dimensions we show that O (n(7/3)) is an upper bound on the number of halving planes for a dense set, The proof is based on a metric argument that can be extended to d greater than or equal to 4 dimensions, where it leads to O (n(d-2/d)) as an upper bound for the number of halving hyperplanes.","lang":"eng"}],"doi":"10.1007/PL00009291","day":"01","date_updated":"2022-08-18T14:08:38Z","citation":{"short":"H. Edelsbrunner, P. Valtr, E. Welzl, Discrete &#38; Computational Geometry 17 (1997) 243–255.","mla":"Edelsbrunner, Herbert, et al. “Cutting Dense Point Sets in Half.” <i>Discrete &#38; Computational Geometry</i>, vol. 17, no. 3, Springer, 1997, pp. 243–55, doi:<a href=\"https://doi.org/10.1007/PL00009291\">10.1007/PL00009291</a>.","ista":"Edelsbrunner H, Valtr P, Welzl E. 1997. Cutting dense point sets in half. Discrete &#38; Computational Geometry. 17(3), 243–255.","apa":"Edelsbrunner, H., Valtr, P., &#38; Welzl, E. (1997). Cutting dense point sets in half. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/PL00009291\">https://doi.org/10.1007/PL00009291</a>","ama":"Edelsbrunner H, Valtr P, Welzl E. Cutting dense point sets in half. <i>Discrete &#38; Computational Geometry</i>. 1997;17(3):243-255. doi:<a href=\"https://doi.org/10.1007/PL00009291\">10.1007/PL00009291</a>","ieee":"H. Edelsbrunner, P. Valtr, and E. Welzl, “Cutting dense point sets in half,” <i>Discrete &#38; Computational Geometry</i>, vol. 17, no. 3. Springer, pp. 243–255, 1997.","chicago":"Edelsbrunner, Herbert, Pavel Valtr, and Emo Welzl. “Cutting Dense Point Sets in Half.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1997. <a href=\"https://doi.org/10.1007/PL00009291\">https://doi.org/10.1007/PL00009291</a>."},"year":"1997","article_type":"original","publisher":"Springer","page":"243 - 255","quality_controlled":"1","title":"Cutting dense point sets in half","intvolume":"        17","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T12:06:29Z","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner"},{"full_name":"Valtr, Pavel","last_name":"Valtr","first_name":"Pavel"},{"full_name":"Welzl, Emo","last_name":"Welzl","first_name":"Emo"}],"issue":"3","_id":"4022","scopus_import":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","publist_id":"2103","publication_identifier":{"issn":["0179-5376"]},"date_published":"1997-04-01T00:00:00Z","type":"journal_article","language":[{"iso":"eng"}],"month":"04","oa_version":"None","publication":"Discrete & Computational Geometry"},{"oa_version":"None","month":"04","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0179-5376"]},"publist_id":"2104","date_published":"1997-04-01T00:00:00Z","type":"journal_article","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T12:06:30Z","title":"Inclusion-exclusion complexes for pseudodisk collections","intvolume":"        17","_id":"4023","scopus_import":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Ramos, Edgar","last_name":"Ramos","first_name":"Edgar"}],"issue":"3","publisher":"Springer","article_type":"original","page":"287 - 306","quality_controlled":"1","doi":"10.1007/PL00009295","day":"01","abstract":[{"text":"Let B be a finite pseudodisk collection in the plane. By the principle of inclusion-exclusion, the area or any other measure of the union is [GRAPHICS] We show the existence of a two-dimensional abstract simplicial complex, X subset of or equal to 2(B), so the above relation holds even if X is substituted for 2(B). In addition, X can be embedded in R(2) SO its underlying space is homotopy equivalent to int Boolean OR B, and the frontier of X is isomorphic to the nerve of the set of boundary contributions.","lang":"eng"}],"date_updated":"2022-08-18T14:39:39Z","citation":{"apa":"Edelsbrunner, H., &#38; Ramos, E. (1997). Inclusion-exclusion complexes for pseudodisk collections. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/PL00009295\">https://doi.org/10.1007/PL00009295</a>","ama":"Edelsbrunner H, Ramos E. Inclusion-exclusion complexes for pseudodisk collections. <i>Discrete &#38; Computational Geometry</i>. 1997;17(3):287-306. doi:<a href=\"https://doi.org/10.1007/PL00009295\">10.1007/PL00009295</a>","ieee":"H. Edelsbrunner and E. Ramos, “Inclusion-exclusion complexes for pseudodisk collections,” <i>Discrete &#38; Computational Geometry</i>, vol. 17, no. 3. Springer, pp. 287–306, 1997.","chicago":"Edelsbrunner, Herbert, and Edgar Ramos. “Inclusion-Exclusion Complexes for Pseudodisk Collections.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1997. <a href=\"https://doi.org/10.1007/PL00009295\">https://doi.org/10.1007/PL00009295</a>.","short":"H. Edelsbrunner, E. Ramos, Discrete &#38; Computational Geometry 17 (1997) 287–306.","mla":"Edelsbrunner, Herbert, and Edgar Ramos. “Inclusion-Exclusion Complexes for Pseudodisk Collections.” <i>Discrete &#38; Computational Geometry</i>, vol. 17, no. 3, Springer, 1997, pp. 287–306, doi:<a href=\"https://doi.org/10.1007/PL00009295\">10.1007/PL00009295</a>.","ista":"Edelsbrunner H, Ramos E. 1997. Inclusion-exclusion complexes for pseudodisk collections. Discrete &#38; Computational Geometry. 17(3), 287–306."},"year":"1997","volume":17,"acknowledgement":"Supported by the National Science Foundation, under Grant ASC-9200301 and the Alan T. Waterman Award CCR-9118874.","extern":"1"},{"date_updated":"2022-06-27T08:14:48Z","year":"1995","citation":{"chicago":"Edelsbrunner, Herbert. “The Union of Balls and Its Dual Shape.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1995. <a href=\"https://doi.org/10.1007/BF02574053\">https://doi.org/10.1007/BF02574053</a>.","ieee":"H. Edelsbrunner, “The union of balls and its dual shape,” <i>Discrete &#38; Computational Geometry</i>, vol. 13, no. 1. Springer, pp. 415–440, 1995.","ama":"Edelsbrunner H. The union of balls and its dual shape. <i>Discrete &#38; Computational Geometry</i>. 1995;13(1):415-440. doi:<a href=\"https://doi.org/10.1007/BF02574053\">10.1007/BF02574053</a>","apa":"Edelsbrunner, H. (1995). The union of balls and its dual shape. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02574053\">https://doi.org/10.1007/BF02574053</a>","ista":"Edelsbrunner H. 1995. The union of balls and its dual shape. Discrete &#38; Computational Geometry. 13(1), 415–440.","mla":"Edelsbrunner, Herbert. “The Union of Balls and Its Dual Shape.” <i>Discrete &#38; Computational Geometry</i>, vol. 13, no. 1, Springer, 1995, pp. 415–40, doi:<a href=\"https://doi.org/10.1007/BF02574053\">10.1007/BF02574053</a>.","short":"H. Edelsbrunner, Discrete &#38; Computational Geometry 13 (1995) 415–440."},"abstract":[{"lang":"eng","text":"Efficient algorithms are described for computing topological, combinatorial, and metric properties of the union of finitely many spherical balls in R(d) These algorithms are based on a simplicial complex dual to a decomposition of the union of balls using Voronoi cells, and on short inclusion-exclusion formulas derived from this complex. The algorithms are most relevant in R(3) where unions of finitely many balls are commonly used as models of molecules."}],"doi":"10.1007/BF02574053","day":"01","extern":"1","acknowledgement":"This work is supported by the National Science Foundation, under Grant ASC-9200301, and the Alan T. Waterman award, Grant CCR-9118874. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the author and do not necessarily reflect the view of the National Science Foundation.","volume":13,"author":[{"first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"issue":"1","_id":"4028","scopus_import":"1","title":"The union of balls and its dual shape","intvolume":"        13","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T12:06:31Z","page":"415 - 440","quality_controlled":"1","article_type":"original","publisher":"Springer","date_published":"1995-12-01T00:00:00Z","type":"journal_article","publist_id":"2095","oa":1,"publication_identifier":{"issn":["0179-5376"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02574053"}],"publication":"Discrete & Computational Geometry","month":"12","oa_version":"Published Version","language":[{"iso":"eng"}]},{"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02574025"}],"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","date_published":"1995-12-01T00:00:00Z","publication_identifier":{"issn":["0179-5376"]},"publist_id":"2094","language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","oa_version":"None","month":"12","volume":13,"acknowledgement":"The authors wish to express their gratitude for the support and hospitality of the DEC Palo Alto Systems Research Center.","extern":"1","citation":{"apa":"Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Sharir, M., &#38; Welzl, E. (1995). Improved bounds on weak ε-nets for convex sets. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02574025\">https://doi.org/10.1007/BF02574025</a>","ama":"Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Sharir M, Welzl E. Improved bounds on weak ε-nets for convex sets. <i>Discrete &#38; Computational Geometry</i>. 1995;13(1):1-15. doi:<a href=\"https://doi.org/10.1007/BF02574025\">10.1007/BF02574025</a>","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, and Emo Welzl. “Improved Bounds on Weak ε-Nets for Convex Sets.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1995. <a href=\"https://doi.org/10.1007/BF02574025\">https://doi.org/10.1007/BF02574025</a>.","ieee":"B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, and E. Welzl, “Improved bounds on weak ε-nets for convex sets,” <i>Discrete &#38; Computational Geometry</i>, vol. 13, no. 1. Springer, pp. 1–15, 1995.","mla":"Chazelle, Bernard, et al. “Improved Bounds on Weak ε-Nets for Convex Sets.” <i>Discrete &#38; Computational Geometry</i>, vol. 13, no. 1, Springer, 1995, pp. 1–15, doi:<a href=\"https://doi.org/10.1007/BF02574025\">10.1007/BF02574025</a>.","short":"B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, E. Welzl, Discrete &#38; Computational Geometry 13 (1995) 1–15.","ista":"Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Sharir M, Welzl E. 1995. Improved bounds on weak ε-nets for convex sets. Discrete &#38; Computational Geometry. 13(1), 1–15."},"year":"1995","date_updated":"2022-06-13T12:37:06Z","day":"01","doi":"10.1007/BF02574025","abstract":[{"lang":"eng","text":"Let S be a set of n points in ℝd . A set W is a weak ε-net for (convex ranges of)S if, for any T⊆S containing εn points, the convex hull of T intersects W. We show the existence of weak ε-nets of size {Mathematical expression}, where β2=0, β3=1, and βd ≈0.149·2d-1(d-1)!, improving a previous bound of Alon et al. Such a net can be computed effectively. We also consider two special cases: when S is a planar point set in convex position, we prove the existence of a net of size O((1/ε) log1.6(1/ε)). In the case where S consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of size O(1/ε), which improves a previous bound of Capoyleas."}],"quality_controlled":"1","page":"1 - 15","publisher":"Springer","article_type":"original","_id":"4035","issue":"1","author":[{"full_name":"Chazelle, Bernard","last_name":"Chazelle","first_name":"Bernard"},{"first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Grigni, Michelangelo","last_name":"Grigni","first_name":"Michelangelo"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}],"date_created":"2018-12-11T12:06:33Z","article_processing_charge":"No","publication_status":"published","intvolume":"        13","title":"Improved bounds on weak ε-nets for convex sets"},{"publication":"Discrete & Computational Geometry","month":"09","oa_version":"None","language":[{"iso":"eng"}],"type":"journal_article","date_published":"1994-09-01T00:00:00Z","publist_id":"2091","publication_identifier":{"issn":["0179-5376"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02574381"}],"issue":"1","author":[{"first_name":"Tamal","last_name":"Dey","full_name":"Dey, Tamal"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"}],"scopus_import":"1","_id":"4032","intvolume":"        12","title":"Counting triangle crossings and halving planes","article_processing_charge":"No","date_created":"2018-12-11T12:06:33Z","publication_status":"published","quality_controlled":"1","page":"281 - 289","article_type":"original","publisher":"Springer","year":"1994","citation":{"ista":"Dey T, Edelsbrunner H. 1994. Counting triangle crossings and halving planes. Discrete &#38; Computational Geometry. 12(1), 281–289.","short":"T. Dey, H. Edelsbrunner, Discrete &#38; Computational Geometry 12 (1994) 281–289.","mla":"Dey, Tamal, and Herbert Edelsbrunner. “Counting Triangle Crossings and Halving Planes.” <i>Discrete &#38; Computational Geometry</i>, vol. 12, no. 1, Springer, 1994, pp. 281–89, doi:<a href=\"https://doi.org/10.1007/BF02574381\">10.1007/BF02574381</a>.","ieee":"T. Dey and H. Edelsbrunner, “Counting triangle crossings and halving planes,” <i>Discrete &#38; Computational Geometry</i>, vol. 12, no. 1. Springer, pp. 281–289, 1994.","chicago":"Dey, Tamal, and Herbert Edelsbrunner. “Counting Triangle Crossings and Halving Planes.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1994. <a href=\"https://doi.org/10.1007/BF02574381\">https://doi.org/10.1007/BF02574381</a>.","ama":"Dey T, Edelsbrunner H. Counting triangle crossings and halving planes. <i>Discrete &#38; Computational Geometry</i>. 1994;12(1):281-289. doi:<a href=\"https://doi.org/10.1007/BF02574381\">10.1007/BF02574381</a>","apa":"Dey, T., &#38; Edelsbrunner, H. (1994). Counting triangle crossings and halving planes. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02574381\">https://doi.org/10.1007/BF02574381</a>"},"date_updated":"2022-06-02T12:53:01Z","abstract":[{"lang":"eng","text":"Every collection of t≥2 n2 triangles with a total of n vertices in ℝ3 has Ω(t4/n6) crossing pairs. This implies that one of their edges meets Ω(t3/n6) of the triangles. From this it follows that n points in ℝ3 have only O(n8/3) halving planes."}],"day":"01","doi":"10.1007/BF02574381","extern":"1","volume":12,"acknowledgement":"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."},{"month":"12","oa_version":"None","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}],"publist_id":"2084","publication_identifier":{"issn":["0179-5376"]},"type":"journal_article","date_published":"1993-12-01T00:00:00Z","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02573974"}],"intvolume":"        10","title":"An upper bound for conforming Delaunay triangulations","date_created":"2018-12-11T12:06:35Z","article_processing_charge":"No","publication_status":"published","issue":"1","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Tan, Tiow","last_name":"Tan","first_name":"Tiow"}],"_id":"4040","article_type":"original","publisher":"Springer","quality_controlled":"1","page":"197 - 213","abstract":[{"lang":"eng","text":"A plane geometric graph C in ℝ2 conforms to another such graph G if each edge of G is the union of some edges of C. It is proved that, for every G with n vertices and m edges, there is a completion of a Delaunay triangulation of O(m2 n) points that conforms to G. The algorithm that constructs the points is also described."}],"day":"01","doi":"10.1007/BF02573974","year":"1993","citation":{"ama":"Edelsbrunner H, Tan T. An upper bound for conforming Delaunay triangulations. <i>Discrete &#38; Computational Geometry</i>. 1993;10(1):197-213. doi:<a href=\"https://doi.org/10.1007/BF02573974\">10.1007/BF02573974</a>","apa":"Edelsbrunner, H., &#38; Tan, T. (1993). An upper bound for conforming Delaunay triangulations. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02573974\">https://doi.org/10.1007/BF02573974</a>","chicago":"Edelsbrunner, Herbert, and Tiow Tan. “An Upper Bound for Conforming Delaunay Triangulations.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1993. <a href=\"https://doi.org/10.1007/BF02573974\">https://doi.org/10.1007/BF02573974</a>.","ieee":"H. Edelsbrunner and T. Tan, “An upper bound for conforming Delaunay triangulations,” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1. Springer, pp. 197–213, 1993.","short":"H. Edelsbrunner, T. Tan, Discrete &#38; Computational Geometry 10 (1993) 197–213.","mla":"Edelsbrunner, Herbert, and Tiow Tan. “An Upper Bound for Conforming Delaunay Triangulations.” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1, Springer, 1993, pp. 197–213, doi:<a href=\"https://doi.org/10.1007/BF02573974\">10.1007/BF02573974</a>.","ista":"Edelsbrunner H, Tan T. 1993. An upper bound for conforming Delaunay triangulations. Discrete &#38; Computational Geometry. 10(1), 197–213."},"date_updated":"2022-03-28T14:58:16Z","extern":"1","volume":10,"acknowledgement":"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. "},{"acknowledgement":"The authors thank two anonymous referees for suggestions on improving the style of this paper. The research of the second' author was supported by the National Science Foundation under Grant No. CCR-8921421 and under the Alan T. Waterman award, Grant No. 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. Part of the work was done while the second, third, and fourth authors visited the Xerox Palo Alto Research Center,\r\nand while the fifth author was on study leave at the University of Illinois. ","volume":10,"extern":"1","citation":{"apa":"Bern, M., Edelsbrunner, H., Eppstein, D., Mitchell, S., &#38; Tan, T. (1993). Edge insertion for optimal triangulations. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02573962\">https://doi.org/10.1007/BF02573962</a>","ama":"Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. Edge insertion for optimal triangulations. <i>Discrete &#38; Computational Geometry</i>. 1993;10(1):47-65. doi:<a href=\"https://doi.org/10.1007/BF02573962\">10.1007/BF02573962</a>","chicago":"Bern, Marshall, Herbert Edelsbrunner, David Eppstein, Stephen Mitchell, and Tiow Tan. “Edge Insertion for Optimal Triangulations.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1993. <a href=\"https://doi.org/10.1007/BF02573962\">https://doi.org/10.1007/BF02573962</a>.","ieee":"M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, and T. Tan, “Edge insertion for optimal triangulations,” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1. Springer, pp. 47–65, 1993.","short":"M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, T. Tan, Discrete &#38; Computational Geometry 10 (1993) 47–65.","mla":"Bern, Marshall, et al. “Edge Insertion for Optimal Triangulations.” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1, Springer, 1993, pp. 47–65, doi:<a href=\"https://doi.org/10.1007/BF02573962\">10.1007/BF02573962</a>.","ista":"Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. 1993. Edge insertion for optimal triangulations. Discrete &#38; Computational Geometry. 10(1), 47–65."},"year":"1993","date_updated":"2022-03-28T14:10:59Z","day":"01","doi":"10.1007/BF02573962","abstract":[{"text":"Edge insertion iteratively improves a triangulation of a finite point set in ℜ2 by adding a new edge, deleting old edges crossing the new edge, and retriangulating the polygonal regions on either side of the new edge. This paper presents an abstract view of the edge insertion paradigm, and then shows that it gives polynomial-time algorithms for several types of optimal triangulations, including minimizing the maximum slope of a piecewise-linear interpolating surface.","lang":"eng"}],"quality_controlled":"1","page":"47 - 65","publisher":"Springer","article_type":"original","scopus_import":"1","_id":"4044","issue":"1","author":[{"full_name":"Bern, Marshall","last_name":"Bern","first_name":"Marshall"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Eppstein, David","first_name":"David","last_name":"Eppstein"},{"full_name":"Mitchell, Stephen","last_name":"Mitchell","first_name":"Stephen"},{"full_name":"Tan, Tiow","first_name":"Tiow","last_name":"Tan"}],"article_processing_charge":"No","date_created":"2018-12-11T12:06:36Z","publication_status":"published","intvolume":"        10","title":"Edge insertion for optimal triangulations","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02573962"}],"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","date_published":"1993-12-01T00:00:00Z","publication_identifier":{"issn":["0179-5376"]},"publist_id":"2082","language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","oa_version":"None","month":"12"},{"doi":"10.1007/BF02573973","day":"01","abstract":[{"lang":"eng","text":"We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε&gt;0, an O(n1+ε) algorithm for computing the diameter of a point set in 3-space, an O(8/5+ε) algorithm for computing the width of such a set, and on O(n8/5+ε) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic."}],"date_updated":"2022-03-28T14:50:42Z","citation":{"mla":"Chazelle, Bernard, et al. “Diameter, Width, Closest Line Pair, and Parametric Searching.” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1, Springer, 1993, pp. 183–96, doi:<a href=\"https://doi.org/10.1007/BF02573973\">10.1007/BF02573973</a>.","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 10 (1993) 183–196.","ista":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1993. Diameter, width, closest line pair, and parametric searching. Discrete &#38; Computational Geometry. 10(1), 183–196.","apa":"Chazelle, B., Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1993). Diameter, width, closest line pair, and parametric searching. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02573973\">https://doi.org/10.1007/BF02573973</a>","ama":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M. Diameter, width, closest line pair, and parametric searching. <i>Discrete &#38; Computational Geometry</i>. 1993;10(1):183-196. doi:<a href=\"https://doi.org/10.1007/BF02573973\">10.1007/BF02573973</a>","ieee":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “Diameter, width, closest line pair, and parametric searching,” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1. Springer, pp. 183–196, 1993.","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir. “Diameter, Width, Closest Line Pair, and Parametric Searching.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1993. <a href=\"https://doi.org/10.1007/BF02573973\">https://doi.org/10.1007/BF02573973</a>."},"year":"1993","volume":10,"acknowledgement":"*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.","extern":"1","publication_status":"published","date_created":"2018-12-11T12:06:37Z","article_processing_charge":"No","title":"Diameter, width, closest line pair, and parametric searching","intvolume":"        10","_id":"4045","scopus_import":"1","author":[{"first_name":"Bernard","last_name":"Chazelle","full_name":"Chazelle, Bernard"},{"last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"}],"issue":"1","publisher":"Springer","article_type":"original","page":"183 - 196","quality_controlled":"1","publication_identifier":{"issn":["0179-5376"]},"publist_id":"2083","date_published":"1993-12-01T00:00:00Z","type":"journal_article","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02573973"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","oa_version":"None","month":"12","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}]},{"volume":6,"acknowledgement":"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).","extern":"1","date_updated":"2022-02-24T15:06:41Z","year":"1991","citation":{"chicago":"Agarwal, Pankaj, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. “Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1991. <a href=\"https://doi.org/10.1007/BF02574698\">https://doi.org/10.1007/BF02574698</a>.","ieee":"P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, “Euclidean minimum spanning trees and bichromatic closest pairs,” <i>Discrete &#38; Computational Geometry</i>, vol. 6, no. 1. Springer, pp. 407–422, 1991.","apa":"Agarwal, P., Edelsbrunner, H., Schwarzkopf, O., &#38; Welzl, E. (1991). Euclidean minimum spanning trees and bichromatic closest pairs. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02574698\">https://doi.org/10.1007/BF02574698</a>","ama":"Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. Euclidean minimum spanning trees and bichromatic closest pairs. <i>Discrete &#38; Computational Geometry</i>. 1991;6(1):407-422. doi:<a href=\"https://doi.org/10.1007/BF02574698\">10.1007/BF02574698</a>","ista":"Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. 1991. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete &#38; Computational Geometry. 6(1), 407–422.","mla":"Agarwal, Pankaj, et al. “Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” <i>Discrete &#38; Computational Geometry</i>, vol. 6, no. 1, Springer, 1991, pp. 407–22, doi:<a href=\"https://doi.org/10.1007/BF02574698\">10.1007/BF02574698</a>.","short":"P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, Discrete &#38; Computational Geometry 6 (1991) 407–422."},"doi":"10.1007/BF02574698","day":"01","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(Fd (N,N) logd N), where Fd (n,m) is the time required to compute a bichromatic closest pair among n red and m green points in Ed . If Fd (N,N)=Ω(N1+ε), for some fixed e{open}&gt;0, then the running time improves to O(Fd (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest 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/3 log4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree of N points in E3. In d≥4 dimensions we obtain expected time O((nm)1-1/([d/2]+1)+ε+m log n+n log m) for the bichromatic closest pair problem and O(N2-2/([d/2]+1)ε) for the Euclidean minimum spanning tree problem, for any positive e{open}."}],"page":"407 - 422","quality_controlled":"1","publisher":"Springer","article_type":"original","_id":"4061","scopus_import":"1","author":[{"first_name":"Pankaj","last_name":"Agarwal","full_name":"Agarwal, Pankaj"},{"last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Schwarzkopf, Otfried","first_name":"Otfried","last_name":"Schwarzkopf"},{"last_name":"Welzl","first_name":"Emo","full_name":"Welzl, Emo"}],"issue":"1","publication_status":"published","date_created":"2018-12-11T12:06:42Z","article_processing_charge":"No","title":"Euclidean minimum spanning trees and bichromatic closest pairs","intvolume":"         6","main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02574698"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","date_published":"1991-12-01T00:00:00Z","type":"journal_article","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"oa":1,"publist_id":"2062","language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","oa_version":"Published Version","month":"12"},{"author":[{"first_name":"Boris","last_name":"Aronov","full_name":"Aronov, Boris"},{"full_name":"Chazelle, Bernard","last_name":"Chazelle","first_name":"Bernard"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"},{"first_name":"Rephael","last_name":"Wenger","full_name":"Wenger, Rephael"}],"issue":"1","_id":"4062","scopus_import":"1","title":"Points and triangles in the plane and halving planes in space","intvolume":"         6","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T12:06:43Z","page":"435 - 442","quality_controlled":"1","article_type":"original","publisher":"Springer","date_updated":"2022-02-24T15:39:25Z","citation":{"mla":"Aronov, Boris, et al. “Points and Triangles in the Plane and Halving Planes in Space.” <i>Discrete &#38; Computational Geometry</i>, vol. 6, no. 1, Springer, 1991, pp. 435–42, doi:<a href=\"https://doi.org/10.1007/BF02574700\">10.1007/BF02574700</a>.","short":"B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, R. Wenger, Discrete &#38; Computational Geometry 6 (1991) 435–442.","ista":"Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. 1991. Points and triangles in the plane and halving planes in space. Discrete &#38; Computational Geometry. 6(1), 435–442.","apa":"Aronov, B., Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Wenger, R. (1991). Points and triangles in the plane and halving planes in space. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02574700\">https://doi.org/10.1007/BF02574700</a>","ama":"Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. Points and triangles in the plane and halving planes in space. <i>Discrete &#38; Computational Geometry</i>. 1991;6(1):435-442. doi:<a href=\"https://doi.org/10.1007/BF02574700\">10.1007/BF02574700</a>","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,” <i>Discrete &#38; Computational Geometry</i>, vol. 6, no. 1. Springer, pp. 435–442, 1991.","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.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1991. <a href=\"https://doi.org/10.1007/BF02574700\">https://doi.org/10.1007/BF02574700</a>."},"year":"1991","abstract":[{"text":"We prove that for any set S of n points in the plane and n3-α triangles spanned by the points in S there exists a point (not necessarily in S) contained in at least n3-3α/(c log5 n) of the triangles. This implies that any set of n points in three-dimensional space defines at most {Mathematical expression} halving planes.","lang":"eng"}],"doi":"10.1007/BF02574700","day":"01","extern":"1","acknowledgement":"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\r\nAcademy of Sciences","volume":6,"publication":"Discrete & Computational Geometry","month":"12","oa_version":"Published Version","language":[{"iso":"eng"}],"date_published":"1991-12-01T00:00:00Z","type":"journal_article","oa":1,"publist_id":"2063","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02574700"}]},{"article_type":"original","publisher":"Springer","quality_controlled":"1","page":"197 - 216","intvolume":"         5","title":"The complexity of many cells in arrangements of planes and related problems","date_created":"2018-12-11T12:06:44Z","article_processing_charge":"No","publication_status":"published","issue":"1","author":[{"orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"}],"scopus_import":"1","_id":"4066","extern":"1","volume":5,"acknowledgement":"Supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by NSF Grant CCR-8714565. Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. I-6-44862 and by NSF Grant CCR-87t4565. Work by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-82-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. An abstract of this\r\npaper has appeared in the Proceedings of the 13th International Mathematical Programming Symposium, Tokyo, 1988, p. 147","abstract":[{"lang":"eng","text":"We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m 2/3 n logn +n 2); we can calculatem such cells specified by a point in each, in worst-case timeO(m 2/3 n log3 n+n 2 logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m 2/3 n logn+n 2), but this number is onlyO(m 3/5– n 4/5+2 +m+n logm), for any&gt;0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m 3/4– n 3/4+3 +m) log2 n+n logn logm) for any&gt;0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m 3/4– n 3/4+3 +m] log2 n+n logn logm) for any&gt;0. (v) The maximum number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d&gt;3, isO(m 2/3 n d/3 logn+n d–1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight."}],"day":"01","doi":"10.1007/BF02187785","year":"1990","citation":{"ama":"Edelsbrunner H, Guibas L, Sharir M. The complexity of many cells in arrangements of planes and related problems. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):197-216. doi:<a href=\"https://doi.org/10.1007/BF02187785\">10.1007/BF02187785</a>","apa":"Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1990). The complexity of many cells in arrangements of planes and related problems. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187785\">https://doi.org/10.1007/BF02187785</a>","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity of Many Cells in Arrangements of Planes and Related Problems.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02187785\">https://doi.org/10.1007/BF02187785</a>.","ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity of many cells in arrangements of planes and related problems,” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 197–216, 1990.","short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 5 (1990) 197–216.","mla":"Edelsbrunner, Herbert, et al. “The Complexity of Many Cells in Arrangements of Planes and Related Problems.” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 197–216, doi:<a href=\"https://doi.org/10.1007/BF02187785\">10.1007/BF02187785</a>.","ista":"Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity of many cells in arrangements of planes and related problems. Discrete &#38; Computational Geometry. 5(1), 197–216."},"date_updated":"2022-02-22T11:02:41Z","language":[{"iso":"eng"}],"month":"03","oa_version":"None","publication":"Discrete & Computational Geometry","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187785"}],"publist_id":"2054","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"type":"journal_article","date_published":"1990-03-01T00:00:00Z"},{"language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","oa_version":"None","month":"01","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187778"}],"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","date_published":"1990-01-01T00:00:00Z","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publist_id":"2057","quality_controlled":"1","page":"35 - 42","publisher":"Springer","article_type":"original","_id":"4068","issue":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"}],"date_created":"2018-12-11T12:06:45Z","article_processing_charge":"No","publication_status":"published","intvolume":"         5","title":"The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2","acknowledgement":"Research of the first author was supported by Amoco Foundation for Faculty Development in Computer Science Grant No. 1-6-44862. Work on this paper by the second author was supported by Office of Naval Research Grant No. N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation.","volume":5,"extern":"1","year":"1990","citation":{"ieee":"H. Edelsbrunner and M. Sharir, “The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2,” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 35–42, 1990.","chicago":"Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02187778\">https://doi.org/10.1007/BF02187778</a>.","apa":"Edelsbrunner, H., &#38; Sharir, M. (1990). The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187778\">https://doi.org/10.1007/BF02187778</a>","ama":"Edelsbrunner H, Sharir M. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):35-42. doi:<a href=\"https://doi.org/10.1007/BF02187778\">10.1007/BF02187778</a>","ista":"Edelsbrunner H, Sharir M. 1990. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. Discrete &#38; Computational Geometry. 5(1), 35–42.","short":"H. Edelsbrunner, M. Sharir, Discrete &#38; Computational Geometry 5 (1990) 35–42.","mla":"Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 35–42, doi:<a href=\"https://doi.org/10.1007/BF02187778\">10.1007/BF02187778</a>."},"date_updated":"2022-02-22T14:50:34Z","day":"01","doi":"10.1007/BF02187778","abstract":[{"lang":"eng","text":"LetS be a collection ofn convex, closed, and pairwise nonintersecting sets in the Euclidean plane labeled from 1 ton. A pair of permutations\r\n(i1i2in−1in)(inin−1i2i1) \r\nis called ageometric permutation of S if there is a line that intersects all sets ofS in this order. We prove thatS can realize at most 2n–2 geometric permutations. This upper bound is tight."}]},{"publisher":"Springer","article_type":"original","quality_controlled":"1","page":"161 - 196","date_created":"2018-12-11T12:06:46Z","article_processing_charge":"No","publication_status":"published","intvolume":"         5","title":"The complexity and construction of many faces in arrangements of lines and of segments","scopus_import":"1","_id":"4072","issue":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"}],"volume":5,"acknowledgement":"The first author is pleased to acknowledge partial support by the Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation under Grant CCR-8714565. Work on this paper by the third author has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant 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 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55.","extern":"1","day":"01","doi":"10.1007/BF02187784","abstract":[{"text":"We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m 2/3– n 2/3+2 +n) for any&gt;0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m 2/3– n 2/3+2 logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m 2/3– n 2/3+2 +n (n) logm) for any&gt;0, where(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m 2/3– n 2/3+2 log+n(n) log2 n logm).","lang":"eng"}],"year":"1990","citation":{"ama":"Edelsbrunner H, Guibas L, Sharir M. The complexity and construction of many faces in arrangements of lines and of segments. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):161-196. doi:<a href=\"https://doi.org/10.1007/BF02187784\">10.1007/BF02187784</a>","apa":"Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1990). The complexity and construction of many faces in arrangements of lines and of segments. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187784\">https://doi.org/10.1007/BF02187784</a>","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02187784\">https://doi.org/10.1007/BF02187784</a>.","ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity and construction of many faces in arrangements of lines and of segments,” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 161–196, 1990.","mla":"Edelsbrunner, Herbert, et al. “The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 161–96, doi:<a href=\"https://doi.org/10.1007/BF02187784\">10.1007/BF02187784</a>.","short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 5 (1990) 161–196.","ista":"Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity and construction of many faces in arrangements of lines and of segments. Discrete &#38; Computational Geometry. 5(1), 161–196."},"date_updated":"2022-02-22T09:27:30Z","language":[{"iso":"eng"}],"oa_version":"None","month":"01","publication":"Discrete & Computational Geometry","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187784"}],"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publist_id":"2053","type":"journal_article","date_published":"1990-01-01T00:00:00Z"},{"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.","volume":5,"extern":"1","doi":"10.1007/BF02187783","day":"01","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"}],"date_updated":"2022-02-17T15:41:04Z","citation":{"ista":"Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. 1990. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete &#38; Computational Geometry. 5(1), 99–160.","short":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Discrete &#38; Computational Geometry 5 (1990) 99–160.","mla":"Clarkson, Kenneth, et al. “Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 99–160, doi:<a href=\"https://doi.org/10.1007/BF02187783\">10.1007/BF02187783</a>.","ieee":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, “Combinatorial complexity bounds for arrangements of curves and spheres,” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 99–160, 1990.","chicago":"Clarkson, Kenneth, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Emo Welzl. “Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02187783\">https://doi.org/10.1007/BF02187783</a>.","apa":"Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Welzl, E. (1990). Combinatorial complexity bounds for arrangements of curves and spheres. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187783\">https://doi.org/10.1007/BF02187783</a>","ama":"Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. Combinatorial complexity bounds for arrangements of curves and spheres. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):99-160. doi:<a href=\"https://doi.org/10.1007/BF02187783\">10.1007/BF02187783</a>"},"year":"1990","publisher":"Springer","article_type":"original","page":"99 - 160","quality_controlled":"1","publication_status":"published","date_created":"2018-12-11T12:06:47Z","article_processing_charge":"No","title":"Combinatorial complexity bounds for arrangements of curves and spheres","intvolume":"         5","_id":"4074","author":[{"last_name":"Clarkson","first_name":"Kenneth","full_name":"Clarkson, Kenneth"},{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"},{"last_name":"Welzl","first_name":"Emo","full_name":"Welzl, Emo"}],"issue":"1","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187783"}],"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publist_id":"2048","date_published":"1990-03-01T00:00:00Z","type":"journal_article","language":[{"iso":"eng"}],"oa_version":"None","month":"03","publication":"Discrete & Computational Geometry"},{"month":"12","oa_version":"Published Version","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}],"publist_id":"2038","oa":1,"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"type":"journal_article","date_published":"1989-12-01T00:00:00Z","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187733","open_access":"1"}],"intvolume":"         4","title":"The upper envelope of piecewise linear functions: Algorithms and applications","date_created":"2018-12-11T12:06:50Z","article_processing_charge":"No","publication_status":"published","issue":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"}],"_id":"4081","article_type":"original","publisher":"Springer","quality_controlled":"1","page":"311 - 336","abstract":[{"lang":"eng","text":"This paper studies applications of envelopes of piecewise linear functions to problems in computational geometry. Among these applications we find problems involving hidden line/surface elimination, motion planning, transversals of polytopes, and a new type of Voronoi diagram for clusters of points. All results are either combinatorial or computational in nature. They are based on the combinatorial analysis in two companion papers [PS] and [E2] and a divide-and-conquer algorithm for computing envelopes described in this paper."}],"day":"01","doi":"10.1007/BF02187733","citation":{"ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The upper envelope of piecewise linear functions: Algorithms and applications,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 311–336, 1989.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187733\">https://doi.org/10.1007/BF02187733</a>.","ama":"Edelsbrunner H, Guibas L, Sharir M. The upper envelope of piecewise linear functions: Algorithms and applications. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):311-336. doi:<a href=\"https://doi.org/10.1007/BF02187733\">10.1007/BF02187733</a>","apa":"Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1989). The upper envelope of piecewise linear functions: Algorithms and applications. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187733\">https://doi.org/10.1007/BF02187733</a>","ista":"Edelsbrunner H, Guibas L, Sharir M. 1989. The upper envelope of piecewise linear functions: Algorithms and applications. Discrete &#38; Computational Geometry. 4(1), 311–336.","short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 4 (1989) 311–336.","mla":"Edelsbrunner, Herbert, et al. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 311–36, doi:<a href=\"https://doi.org/10.1007/BF02187733\">10.1007/BF02187733</a>."},"year":"1989","date_updated":"2022-02-10T15:53:48Z","extern":"1","volume":4,"acknowledgement":"Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862. Work by the third author has been supported by the Office of Naval Research Grant N00014-82-K-0381, 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 NCRD, the Israeli National Council for Research and Development."},{"language":[{"iso":"eng"}],"oa_version":"Published Version","month":"11","publication":"Discrete & Computational Geometry","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187734","open_access":"1"}],"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"oa":1,"publist_id":"2034","date_published":"1989-11-01T00:00:00Z","type":"journal_article","publisher":"Springer","article_type":"original","page":"337 - 343","quality_controlled":"1","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T12:06:51Z","title":"The upper envelope of piecewise linear functions: Tight bounds on the number of faces ","intvolume":"         4","_id":"4086","scopus_import":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner"}],"issue":"4","volume":4,"acknowledgement":"This work was supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under Grant CCR-8714565. Research on the presented result was partially carried out while the author worked for the IBM T. J. Watson Research Center at Yorktown Height, New York, USA. \r\n","extern":"1","doi":"10.1007/BF02187734","day":"01","abstract":[{"text":"This note proves that the maximum number of faces (of any dimension) of the upper envelope of a set ofn possibly intersectingd-simplices ind+1 dimensions is (n d (n)). This is an extension of a result of Pach and Sharir [PS] who prove the same bound for the number ofd-dimensional faces of the upper envelope.","lang":"eng"}],"date_updated":"2022-02-10T11:08:12Z","citation":{"ista":"Edelsbrunner H. 1989. The upper envelope of piecewise linear functions: Tight bounds on the number of faces . Discrete &#38; Computational Geometry. 4(4), 337–343.","mla":"Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions: Tight Bounds on the Number of Faces .” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 4, Springer, 1989, pp. 337–43, doi:<a href=\"https://doi.org/10.1007/BF02187734\">10.1007/BF02187734</a>.","short":"H. Edelsbrunner, Discrete &#38; Computational Geometry 4 (1989) 337–343.","chicago":"Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions: Tight Bounds on the Number of Faces .” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187734\">https://doi.org/10.1007/BF02187734</a>.","ieee":"H. Edelsbrunner, “The upper envelope of piecewise linear functions: Tight bounds on the number of faces ,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 4. Springer, pp. 337–343, 1989.","apa":"Edelsbrunner, H. (1989). The upper envelope of piecewise linear functions: Tight bounds on the number of faces . <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187734\">https://doi.org/10.1007/BF02187734</a>","ama":"Edelsbrunner H. The upper envelope of piecewise linear functions: Tight bounds on the number of faces . <i>Discrete &#38; Computational Geometry</i>. 1989;4(4):337-343. doi:<a href=\"https://doi.org/10.1007/BF02187734\">10.1007/BF02187734</a>"},"year":"1989"}]