[{"intvolume":"        10","status":"public","day":"01","type":"journal_article","issue":"3-4","publication":"Journal of Symbolic Computation","page":"335 - 347","publisher":"Elsevier","scopus_import":"1","language":[{"iso":"eng"}],"month":"01","date_published":"1990-01-01T00:00:00Z","article_type":"original","date_created":"2018-12-11T12:06:42Z","abstract":[{"text":"This paper offers combinatorial results on extremum problems concerning the number of tetrahedra in a tetrahedrization of n points in general position in three dimensions, i.e. such that no four points are co-planar, It also presents an algorithm that in O(n log n) time constructs a tetrahedrization of a set of n points consisting of at most 3n-11 tetrahedra.","lang":"eng"}],"author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"first_name":"Franco","full_name":"Preparata, Franco","last_name":"Preparata"},{"full_name":"West, Douglas","last_name":"West","first_name":"Douglas"}],"publication_status":"published","citation":{"ista":"Edelsbrunner H, Preparata F, West D. 1990. Tetrahedrizing point sets in three dimensions. Journal of Symbolic Computation. 10(3–4), 335–347.","short":"H. Edelsbrunner, F. Preparata, D. West, Journal of Symbolic Computation 10 (1990) 335–347.","ama":"Edelsbrunner H, Preparata F, West D. Tetrahedrizing point sets in three dimensions. <i>Journal of Symbolic Computation</i>. 1990;10(3-4):335-347. doi:<a href=\"https://doi.org/10.1016/S0747-7171(08)80068-5\">10.1016/S0747-7171(08)80068-5</a>","mla":"Edelsbrunner, Herbert, et al. “Tetrahedrizing Point Sets in Three Dimensions.” <i>Journal of Symbolic Computation</i>, vol. 10, no. 3–4, Elsevier, 1990, pp. 335–47, doi:<a href=\"https://doi.org/10.1016/S0747-7171(08)80068-5\">10.1016/S0747-7171(08)80068-5</a>.","chicago":"Edelsbrunner, Herbert, Franco Preparata, and Douglas West. “Tetrahedrizing Point Sets in Three Dimensions.” <i>Journal of Symbolic Computation</i>. Elsevier, 1990. <a href=\"https://doi.org/10.1016/S0747-7171(08)80068-5\">https://doi.org/10.1016/S0747-7171(08)80068-5</a>.","ieee":"H. Edelsbrunner, F. Preparata, and D. West, “Tetrahedrizing point sets in three dimensions,” <i>Journal of Symbolic Computation</i>, vol. 10, no. 3–4. Elsevier, pp. 335–347, 1990.","apa":"Edelsbrunner, H., Preparata, F., &#38; West, D. (1990). Tetrahedrizing point sets in three dimensions. <i>Journal of Symbolic Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/S0747-7171(08)80068-5\">https://doi.org/10.1016/S0747-7171(08)80068-5</a>"},"_id":"4060","extern":"1","publication_identifier":{"eissn":["1095-855X"],"issn":["0747-7171"]},"acknowledgement":"Research of the first author is supported by Amoco Fnd. Fac. Dec. Comput. Sci. 1-6-44862, the second author is supported by NSF Grant ECS 84-10902, and research of the third author is supported in part by ONR Grant N00014-85K0570 and by NSF Grant DMS 8504322.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","quality_controlled":"1","oa_version":"Published Version","publist_id":"2061","volume":10,"date_updated":"2022-02-23T10:10:35Z","oa":1,"article_processing_charge":"No","title":"Tetrahedrizing point sets in three dimensions","doi":"10.1016/S0747-7171(08)80068-5","year":"1990","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/S0747717108800685?via%3Dihub","open_access":"1"}]},{"citation":{"apa":"Edelsbrunner, H., &#38; Waupotitsch, R. (1986). Computing a ham-sandwich cut in two dimensions. <i>Journal of Symbolic Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/S0747-7171(86)80020-7\">https://doi.org/10.1016/S0747-7171(86)80020-7</a>","ieee":"H. Edelsbrunner and R. Waupotitsch, “Computing a ham-sandwich cut in two dimensions,” <i>Journal of Symbolic Computation</i>, vol. 2, no. 2. Elsevier, pp. 171–178, 1986.","chicago":"Edelsbrunner, Herbert, and Roman Waupotitsch. “Computing a Ham-Sandwich Cut in Two Dimensions.” <i>Journal of Symbolic Computation</i>. Elsevier, 1986. <a href=\"https://doi.org/10.1016/S0747-7171(86)80020-7\">https://doi.org/10.1016/S0747-7171(86)80020-7</a>.","mla":"Edelsbrunner, Herbert, and Roman Waupotitsch. “Computing a Ham-Sandwich Cut in Two Dimensions.” <i>Journal of Symbolic Computation</i>, vol. 2, no. 2, Elsevier, 1986, pp. 171–78, doi:<a href=\"https://doi.org/10.1016/S0747-7171(86)80020-7\">10.1016/S0747-7171(86)80020-7</a>.","ama":"Edelsbrunner H, Waupotitsch R. Computing a ham-sandwich cut in two dimensions. <i>Journal of Symbolic Computation</i>. 1986;2(2):171-178. doi:<a href=\"https://doi.org/10.1016/S0747-7171(86)80020-7\">10.1016/S0747-7171(86)80020-7</a>","short":"H. Edelsbrunner, R. Waupotitsch, Journal of Symbolic Computation 2 (1986) 171–178.","ista":"Edelsbrunner H, Waupotitsch R. 1986. Computing a ham-sandwich cut in two dimensions. Journal of Symbolic Computation. 2(2), 171–178."},"publication_status":"published","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"last_name":"Waupotitsch","full_name":"Waupotitsch, Roman","first_name":"Roman"}],"abstract":[{"text":"Let B be a set of nb black points and W a set of nw, white points in the Euclidean plane. A line h is said to bisect B (or W) if, at most, half of the points of B (or W) lie on any one side of h. A line that bisects both B and W is called a ham-sandwich cut of B and W. We give an algorithm that computes a ham-sandwich cut of B and W in 0((nh+nw) log (min {nb, nw}+ 1)) time. The algorithm is considerably simpler than the previous most efficient one which takes 0((nb + nw) log (nb + nw)) time.","lang":"eng"}],"article_processing_charge":"No","volume":2,"date_updated":"2022-02-01T11:22:59Z","publist_id":"2018","oa_version":"None","quality_controlled":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","publication_identifier":{"issn":["0747-7171"],"eissn":["1095-855X"]},"_id":"4106","doi":"10.1016/S0747-7171(86)80020-7","year":"1986","title":"Computing a ham-sandwich cut in two dimensions","type":"journal_article","day":"01","status":"public","intvolume":"         2","page":"171 - 178","publication":"Journal of Symbolic Computation","issue":"2","article_type":"original","date_published":"1986-01-01T00:00:00Z","month":"01","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Elsevier","date_created":"2018-12-11T12:06:58Z"},{"publist_id":"2004","volume":1,"date_updated":"2022-01-31T09:20:18Z","oa":1,"article_processing_charge":"No","acknowledgement":"The first author was supported i~1 part by NSF grants MCS 83-03925 and the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-g3-K-0146 and ARPA Order No. 4786.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"Published Version","quality_controlled":"1","_id":"4120","publication_identifier":{"issn":["0747-7171"],"eissn":["1095-855X"]},"extern":"1","publication_status":"published","citation":{"ama":"Chazelle B, Edelsbrunner H. Optimal solutions for a class of point retrieval problems. <i>Journal of Symbolic Computation</i>. 1985;1(1):47-56. doi:<a href=\"https://doi.org/10.1016/S0747-7171(85)80028-6\">10.1016/S0747-7171(85)80028-6</a>","mla":"Chazelle, Bernard, and Herbert Edelsbrunner. “Optimal Solutions for a Class of Point Retrieval Problems.” <i>Journal of Symbolic Computation</i>, vol. 1, no. 1, Elsevier, 1985, pp. 47–56, doi:<a href=\"https://doi.org/10.1016/S0747-7171(85)80028-6\">10.1016/S0747-7171(85)80028-6</a>.","ista":"Chazelle B, Edelsbrunner H. 1985. Optimal solutions for a class of point retrieval problems. Journal of Symbolic Computation. 1(1), 47–56.","short":"B. Chazelle, H. Edelsbrunner, Journal of Symbolic Computation 1 (1985) 47–56.","ieee":"B. Chazelle and H. Edelsbrunner, “Optimal solutions for a class of point retrieval problems,” <i>Journal of Symbolic Computation</i>, vol. 1, no. 1. Elsevier, pp. 47–56, 1985.","apa":"Chazelle, B., &#38; Edelsbrunner, H. (1985). Optimal solutions for a class of point retrieval problems. <i>Journal of Symbolic Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/S0747-7171(85)80028-6\">https://doi.org/10.1016/S0747-7171(85)80028-6</a>","chicago":"Chazelle, Bernard, and Herbert Edelsbrunner. “Optimal Solutions for a Class of Point Retrieval Problems.” <i>Journal of Symbolic Computation</i>. Elsevier, 1985. <a href=\"https://doi.org/10.1016/S0747-7171(85)80028-6\">https://doi.org/10.1016/S0747-7171(85)80028-6</a>."},"author":[{"first_name":"Bernard","full_name":"Chazelle, Bernard","last_name":"Chazelle"},{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"lang":"eng","text":"Let P be a set of n points in the Euclidean plane and let C be a convex figure. We study the problem of preprocessing P so that for any query point q, the points of P in C+q can be retrieved efficiently. If constant time sumces for deciding the inclusion of a point in C, we then demonstrate the existence of an optimal solution: the algorithm requires O(n) space and O(k + log n) time for a query with output size k. If C is a disk, the problem becomes the wellknown fixed-radius neighbour problem, to which we thus provide the first known optimal solution."}],"main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/S0747717185800286?via%3Dihub","open_access":"1"}],"doi":"10.1016/S0747-7171(85)80028-6","year":"1985","title":"Optimal solutions for a class of point retrieval problems","page":"47 - 56","issue":"1","publication":"Journal of Symbolic Computation","type":"journal_article","day":"01","status":"public","intvolume":"         1","date_created":"2018-12-11T12:07:03Z","date_published":"1985-03-01T00:00:00Z","article_type":"original","month":"03","language":[{"iso":"eng"}],"publisher":"Elsevier"}]