[{"language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Elsevier","article_type":"original","date_published":"1990-01-01T00:00:00Z","month":"01","date_created":"2018-12-11T12:06:42Z","status":"public","intvolume":"        10","type":"journal_article","day":"01","page":"335 - 347","publication":"Journal of Symbolic Computation","issue":"3-4","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"}],"author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"first_name":"Franco","last_name":"Preparata","full_name":"Preparata, Franco"},{"first_name":"Douglas","last_name":"West","full_name":"West, Douglas"}],"abstract":[{"lang":"eng","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."}],"citation":{"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>","short":"H. Edelsbrunner, F. Preparata, D. West, Journal of Symbolic Computation 10 (1990) 335–347.","ista":"Edelsbrunner H, Preparata F, West D. 1990. Tetrahedrizing point sets in three dimensions. Journal of Symbolic Computation. 10(3–4), 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>."},"publication_status":"published","oa_version":"Published Version","quality_controlled":"1","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","extern":"1","publication_identifier":{"eissn":["1095-855X"],"issn":["0747-7171"]},"_id":"4060","article_processing_charge":"No","oa":1,"publist_id":"2061","volume":10,"date_updated":"2022-02-23T10:10:35Z"},{"title":"Computing a ham-sandwich cut in two dimensions","doi":"10.1016/S0747-7171(86)80020-7","year":"1986","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","first_name":"Herbert"},{"full_name":"Waupotitsch, Roman","last_name":"Waupotitsch","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"}],"publication_status":"published","citation":{"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>","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>.","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.","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.","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>","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>."},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","quality_controlled":"1","oa_version":"None","_id":"4106","publication_identifier":{"eissn":["1095-855X"],"issn":["0747-7171"]},"extern":"1","publist_id":"2018","volume":2,"date_updated":"2022-02-01T11:22:59Z","article_processing_charge":"No","language":[{"iso":"eng"}],"publisher":"Elsevier","scopus_import":"1","date_published":"1986-01-01T00:00:00Z","article_type":"original","month":"01","date_created":"2018-12-11T12:06:58Z","status":"public","intvolume":"         2","type":"journal_article","day":"01","page":"171 - 178","issue":"2","publication":"Journal of Symbolic Computation"},{"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>.","short":"B. Chazelle, H. Edelsbrunner, Journal of Symbolic Computation 1 (1985) 47–56.","ista":"Chazelle B, Edelsbrunner H. 1985. Optimal solutions for a class of point retrieval problems. Journal of Symbolic Computation. 1(1), 47–56.","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>","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.","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>."},"publication_status":"published","author":[{"last_name":"Chazelle","full_name":"Chazelle, Bernard","first_name":"Bernard"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","first_name":"Herbert"}],"abstract":[{"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.","lang":"eng"}],"article_processing_charge":"No","volume":1,"publist_id":"2004","date_updated":"2022-01-31T09:20:18Z","oa":1,"oa_version":"Published Version","quality_controlled":"1","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","extern":"1","publication_identifier":{"issn":["0747-7171"],"eissn":["1095-855X"]},"_id":"4120","year":"1985","doi":"10.1016/S0747-7171(85)80028-6","title":"Optimal solutions for a class of point retrieval problems","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/S0747717185800286?via%3Dihub","open_access":"1"}],"type":"journal_article","day":"01","status":"public","intvolume":"         1","page":"47 - 56","publication":"Journal of Symbolic Computation","issue":"1","article_type":"original","date_published":"1985-03-01T00:00:00Z","month":"03","language":[{"iso":"eng"}],"publisher":"Elsevier","date_created":"2018-12-11T12:07:03Z"}]