[{"month":"02","date_published":"2013-02-15T00:00:00Z","article_type":"original","publisher":"Elsevier","scopus_import":"1","language":[{"iso":"eng"}],"date_created":"2022-08-08T11:29:08Z","day":"15","type":"journal_article","intvolume":"       113","status":"public","issue":"3","publication":"Information Processing Letters","page":"67-73","doi":"10.1016/j.ipl.2012.11.006","year":"2013","external_id":{"arxiv":["0912.1934"]},"title":"Sponsored search, market equilibria, and the Hungarian Method","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/0912.1934"}],"publication_status":"published","citation":{"apa":"Dütting, P., Henzinger, M. H., &#38; Weber, I. (2013). Sponsored search, market equilibria, and the Hungarian Method. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ipl.2012.11.006\">https://doi.org/10.1016/j.ipl.2012.11.006</a>","ieee":"P. Dütting, M. H. Henzinger, and I. Weber, “Sponsored search, market equilibria, and the Hungarian Method,” <i>Information Processing Letters</i>, vol. 113, no. 3. Elsevier, pp. 67–73, 2013.","chicago":"Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Sponsored Search, Market Equilibria, and the Hungarian Method.” <i>Information Processing Letters</i>. Elsevier, 2013. <a href=\"https://doi.org/10.1016/j.ipl.2012.11.006\">https://doi.org/10.1016/j.ipl.2012.11.006</a>.","mla":"Dütting, Paul, et al. “Sponsored Search, Market Equilibria, and the Hungarian Method.” <i>Information Processing Letters</i>, vol. 113, no. 3, Elsevier, 2013, pp. 67–73, doi:<a href=\"https://doi.org/10.1016/j.ipl.2012.11.006\">10.1016/j.ipl.2012.11.006</a>.","ama":"Dütting P, Henzinger MH, Weber I. Sponsored search, market equilibria, and the Hungarian Method. <i>Information Processing Letters</i>. 2013;113(3):67-73. doi:<a href=\"https://doi.org/10.1016/j.ipl.2012.11.006\">10.1016/j.ipl.2012.11.006</a>","short":"P. Dütting, M.H. Henzinger, I. Weber, Information Processing Letters 113 (2013) 67–73.","ista":"Dütting P, Henzinger MH, Weber I. 2013. Sponsored search, market equilibria, and the Hungarian Method. Information Processing Letters. 113(3), 67–73."},"abstract":[{"lang":"eng","text":"Matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market. Here, as in other markets of that kind, market equilibria correspond to feasible, envy free, and bidder optimal outcomes. For settings without budgets such an outcome always exists and can be computed in polynomial-time by the so-called Hungarian Method. Moreover, every mechanism that computes such an outcome is incentive compatible. We show that the Hungarian Method can be modified so that it finds a feasible, envy free, and bidder optimal outcome for settings with budgets. We also show that in settings with budgets no mechanism that computes such an outcome can be incentive compatible for all inputs. For inputs in general position, however, the presented mechanism—as any other mechanism that computes such an outcome for settings with budgets—is incentive compatible."}],"author":[{"full_name":"Dütting, Paul","last_name":"Dütting","first_name":"Paul"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"first_name":"Ingmar","last_name":"Weber","full_name":"Weber, Ingmar"}],"arxiv":1,"date_updated":"2022-09-12T09:36:15Z","oa":1,"volume":113,"article_processing_charge":"No","_id":"11759","extern":"1","publication_identifier":{"issn":["0020-0190"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","oa_version":"Preprint"},{"_id":"11760","extern":"1","publication_identifier":{"issn":["0020-0190"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","oa_version":"None","issue":"4","publication":"Information Processing Letters","volume":111,"date_updated":"2022-09-12T09:38:05Z","page":"178-183","article_processing_charge":"No","abstract":[{"text":"We study a novel load balancing problem that arises in web search engines. The problem is a combination of an offline assignment problem, where files need to be (copied and) assigned to machines, and an online load balancing problem, where requests ask for specific files and need to be assigned to a corresponding machine, whose load is increased\r\nby this. We present simple deterministic algorithms for this problem and exhibit an interesting trade-off between the available space to make file copies and the obtainable makespan. We also give non-trivial lower bounds for a large class of deterministic algorithms and present a randomized algorithm that beats these bounds with high probability.","lang":"eng"}],"intvolume":"       111","status":"public","author":[{"full_name":"Dütting, Paul","last_name":"Dütting","first_name":"Paul"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"Ingmar","full_name":"Weber, Ingmar","last_name":"Weber"}],"publication_status":"published","day":"15","citation":{"ama":"Dütting P, Henzinger MH, Weber I. Offline file assignments for online load balancing. <i>Information Processing Letters</i>. 2011;111(4):178-183. doi:<a href=\"https://doi.org/10.1016/j.ipl.2010.11.022\">10.1016/j.ipl.2010.11.022</a>","mla":"Dütting, Paul, et al. “Offline File Assignments for Online Load Balancing.” <i>Information Processing Letters</i>, vol. 111, no. 4, Elsevier, 2011, pp. 178–83, doi:<a href=\"https://doi.org/10.1016/j.ipl.2010.11.022\">10.1016/j.ipl.2010.11.022</a>.","short":"P. Dütting, M.H. Henzinger, I. Weber, Information Processing Letters 111 (2011) 178–183.","ista":"Dütting P, Henzinger MH, Weber I. 2011. Offline file assignments for online load balancing. Information Processing Letters. 111(4), 178–183.","ieee":"P. Dütting, M. H. Henzinger, and I. Weber, “Offline file assignments for online load balancing,” <i>Information Processing Letters</i>, vol. 111, no. 4. Elsevier, pp. 178–183, 2011.","apa":"Dütting, P., Henzinger, M. H., &#38; Weber, I. (2011). Offline file assignments for online load balancing. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ipl.2010.11.022\">https://doi.org/10.1016/j.ipl.2010.11.022</a>","chicago":"Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Offline File Assignments for Online Load Balancing.” <i>Information Processing Letters</i>. Elsevier, 2011. <a href=\"https://doi.org/10.1016/j.ipl.2010.11.022\">https://doi.org/10.1016/j.ipl.2010.11.022</a>."},"type":"journal_article","date_created":"2022-08-08T11:33:03Z","publisher":"Elsevier","scopus_import":"1","title":"Offline file assignments for online load balancing","language":[{"iso":"eng"}],"year":"2011","doi":"10.1016/j.ipl.2010.11.022","month":"01","article_type":"original","date_published":"2011-01-15T00:00:00Z"},{"oa_version":"None","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","publication_identifier":{"issn":["0020-0190"]},"_id":"11761","page":"41-44","article_processing_charge":"No","volume":59,"date_updated":"2022-09-12T09:39:51Z","publication":"Information Processing Letters","issue":"1","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"last_name":"Williamson","full_name":"Williamson, David P.","first_name":"David P."}],"status":"public","abstract":[{"lang":"eng","text":"We prove that in an undirected graph there are at most O(n²) cuts of size strictly less than of the size of the minimum cut."}],"intvolume":"        59","type":"journal_article","day":"08","citation":{"ieee":"M. H. Henzinger and D. P. Williamson, “On the number of small cuts in a graph,” <i>Information Processing Letters</i>, vol. 59, no. 1. Elsevier, pp. 41–44, 1996.","apa":"Henzinger, M. H., &#38; Williamson, D. P. (1996). On the number of small cuts in a graph. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(96)00079-8\">https://doi.org/10.1016/0020-0190(96)00079-8</a>","chicago":"Henzinger, Monika H, and David P. Williamson. “On the Number of Small Cuts in a Graph.” <i>Information Processing Letters</i>. Elsevier, 1996. <a href=\"https://doi.org/10.1016/0020-0190(96)00079-8\">https://doi.org/10.1016/0020-0190(96)00079-8</a>.","mla":"Henzinger, Monika H., and David P. Williamson. “On the Number of Small Cuts in a Graph.” <i>Information Processing Letters</i>, vol. 59, no. 1, Elsevier, 1996, pp. 41–44, doi:<a href=\"https://doi.org/10.1016/0020-0190(96)00079-8\">10.1016/0020-0190(96)00079-8</a>.","ama":"Henzinger MH, Williamson DP. On the number of small cuts in a graph. <i>Information Processing Letters</i>. 1996;59(1):41-44. doi:<a href=\"https://doi.org/10.1016/0020-0190(96)00079-8\">10.1016/0020-0190(96)00079-8</a>","ista":"Henzinger MH, Williamson DP. 1996. On the number of small cuts in a graph. Information Processing Letters. 59(1), 41–44.","short":"M.H. Henzinger, D.P. Williamson, Information Processing Letters 59 (1996) 41–44."},"publication_status":"published","date_created":"2022-08-08T11:49:48Z","language":[{"iso":"eng"}],"title":"On the number of small cuts in a graph","scopus_import":"1","publisher":"Elsevier","date_published":"1996-07-08T00:00:00Z","article_type":"original","month":"07","doi":"10.1016/0020-0190(96)00079-8","year":"1996"},{"article_type":"original","date_published":"1992-04-27T00:00:00Z","month":"04","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Elsevier","date_created":"2018-12-11T12:06:38Z","type":"journal_article","day":"27","status":"public","intvolume":"        42","page":"55 - 60","publication":"Information Processing Letters","issue":"1","doi":"10.1016/0020-0190(92)90133-G","year":"1992","title":"Optimal time bounds for some proximity problems in the plane","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/002001909290133G"}],"citation":{"mla":"Aggarwal, Alok, et al. “Optimal Time Bounds for Some Proximity Problems in the Plane.” <i>Information Processing Letters</i>, vol. 42, no. 1, Elsevier, 1992, pp. 55–60, doi:<a href=\"https://doi.org/10.1016/0020-0190(92)90133-G\">10.1016/0020-0190(92)90133-G</a>.","ama":"Aggarwal A, Edelsbrunner H, Raghavan P, Tiwari P. Optimal time bounds for some proximity problems in the plane. <i>Information Processing Letters</i>. 1992;42(1):55-60. doi:<a href=\"https://doi.org/10.1016/0020-0190(92)90133-G\">10.1016/0020-0190(92)90133-G</a>","short":"A. Aggarwal, H. Edelsbrunner, P. Raghavan, P. Tiwari, Information Processing Letters 42 (1992) 55–60.","ista":"Aggarwal A, Edelsbrunner H, Raghavan P, Tiwari P. 1992. Optimal time bounds for some proximity problems in the plane. Information Processing Letters. 42(1), 55–60.","apa":"Aggarwal, A., Edelsbrunner, H., Raghavan, P., &#38; Tiwari, P. (1992). Optimal time bounds for some proximity problems in the plane. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(92)90133-G\">https://doi.org/10.1016/0020-0190(92)90133-G</a>","ieee":"A. Aggarwal, H. Edelsbrunner, P. Raghavan, and P. Tiwari, “Optimal time bounds for some proximity problems in the plane,” <i>Information Processing Letters</i>, vol. 42, no. 1. Elsevier, pp. 55–60, 1992.","chicago":"Aggarwal, Alok, Herbert Edelsbrunner, Prabhakar Raghavan, and Prasoon Tiwari. “Optimal Time Bounds for Some Proximity Problems in the Plane.” <i>Information Processing Letters</i>. Elsevier, 1992. <a href=\"https://doi.org/10.1016/0020-0190(92)90133-G\">https://doi.org/10.1016/0020-0190(92)90133-G</a>."},"publication_status":"published","author":[{"first_name":"Alok","last_name":"Aggarwal","full_name":"Aggarwal, Alok"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"first_name":"Prabhakar","last_name":"Raghavan","full_name":"Raghavan, Prabhakar"},{"first_name":"Prasoon","last_name":"Tiwari","full_name":"Tiwari, Prasoon"}],"abstract":[{"text":"Given a sequence of n points that form the vertices of a simple polygon, we show that determining a closest pair requires OMEGA(n log n) time in the algebraic decision tree model. Together with the well-known O(n log n) upper bound for finding a closest pair, this settles an open problem of Lee and Preparata. We also extend this O(n log n) upper bound to the following problem: Given a collection of sets with a total of n points in the plane, find for each point a closest neighbor that does not belong to the same set.","lang":"eng"}],"article_processing_charge":"No","publist_id":"2080","date_updated":"2022-03-16T09:20:13Z","volume":42,"quality_controlled":"1","oa_version":"None","acknowledgement":"Research supported by the National Science Foundation under Grant CCR-8714565.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"eissn":["1872-6119"],"issn":["0020-0190"]},"extern":"1","_id":"4048"},{"issue":"3","publication":"Information Processing Letters","page":"135 - 141","intvolume":"        43","status":"public","day":"14","type":"journal_article","date_created":"2018-12-11T12:09:16Z","publisher":"Elsevier","scopus_import":"1","language":[{"iso":"eng"}],"month":"09","date_published":"1992-09-14T00:00:00Z","article_type":"original","_id":"4517","extern":"1","publication_identifier":{"issn":["0020-0190"]},"acknowledgement":"The author thanks Martin Abadi, Rajeev Alur, David Dill, Leslie Lamport, Zohar Manna, Amir Pnueli, Fred Schneider, and two anonymous referees for many valuable suggestions and improvements. ","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","quality_controlled":"1","date_updated":"2022-03-07T11:31:23Z","volume":43,"publist_id":"211","article_processing_charge":"No","abstract":[{"text":"It has been observed repeatedly that the standard safety-liveness classification for properties of reactive systems does not fit for real-time properties. This is because the implicit “liveliness” of time shifts the spectrum towards the safety side. While, for example, response—that “something good” will happen eventually—is a classical liveness property, bounded response—that “something good” will happen soon, within a certain amount of time—has many characteristics of safety. We account for this phenomenon formally by defining safety and liveness relative to a given condition, such as the progress of time.","lang":"eng"}],"author":[{"first_name":"Thomas A","last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","citation":{"chicago":"Henzinger, Thomas A. “Sooner Is Safer Than Later.” <i>Information Processing Letters</i>. Elsevier, 1992. <a href=\"https://doi.org/10.1016/0020-0190(92)90005-G\">https://doi.org/10.1016/0020-0190(92)90005-G</a>.","apa":"Henzinger, T. A. (1992). Sooner Is Safer Than Later. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(92)90005-G\">https://doi.org/10.1016/0020-0190(92)90005-G</a>","ieee":"T. A. Henzinger, “Sooner Is Safer Than Later,” <i>Information Processing Letters</i>, vol. 43, no. 3. Elsevier, pp. 135–141, 1992.","short":"T.A. Henzinger, Information Processing Letters 43 (1992) 135–141.","ista":"Henzinger TA. 1992. Sooner Is Safer Than Later. Information Processing Letters. 43(3), 135–141.","ama":"Henzinger TA. Sooner Is Safer Than Later. <i>Information Processing Letters</i>. 1992;43(3):135-141. doi:<a href=\"https://doi.org/10.1016/0020-0190(92)90005-G\">10.1016/0020-0190(92)90005-G</a>","mla":"Henzinger, Thomas A. “Sooner Is Safer Than Later.” <i>Information Processing Letters</i>, vol. 43, no. 3, Elsevier, 1992, pp. 135–41, doi:<a href=\"https://doi.org/10.1016/0020-0190(92)90005-G\">10.1016/0020-0190(92)90005-G</a>."},"main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/002001909290005G?via%3Dihub"}],"title":"Sooner Is Safer Than Later","year":"1992","doi":"10.1016/0020-0190(92)90005-G"},{"citation":{"short":"H. Edelsbrunner, X. Shen, Information Processing Letters 26 (1987) 61–64.","ista":"Edelsbrunner H, Shen X. 1987. A tight lower bound on the size of visibility graphs. Information Processing Letters. 26(2), 61–64.","ama":"Edelsbrunner H, Shen X. A tight lower bound on the size of visibility graphs. <i>Information Processing Letters</i>. 1987;26(2):61-64. doi:<a href=\"https://doi.org/10.1016/0020-0190(87)90038-X\">10.1016/0020-0190(87)90038-X</a>","mla":"Edelsbrunner, Herbert, and Xiaojun Shen. “A Tight Lower Bound on the Size of Visibility Graphs.” <i>Information Processing Letters</i>, vol. 26, no. 2, Elsevier, 1987, pp. 61–64, doi:<a href=\"https://doi.org/10.1016/0020-0190(87)90038-X\">10.1016/0020-0190(87)90038-X</a>.","chicago":"Edelsbrunner, Herbert, and Xiaojun Shen. “A Tight Lower Bound on the Size of Visibility Graphs.” <i>Information Processing Letters</i>. Elsevier, 1987. <a href=\"https://doi.org/10.1016/0020-0190(87)90038-X\">https://doi.org/10.1016/0020-0190(87)90038-X</a>.","ieee":"H. Edelsbrunner and X. Shen, “A tight lower bound on the size of visibility graphs,” <i>Information Processing Letters</i>, vol. 26, no. 2. Elsevier, pp. 61–64, 1987.","apa":"Edelsbrunner, H., &#38; Shen, X. (1987). A tight lower bound on the size of visibility graphs. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(87)90038-X\">https://doi.org/10.1016/0020-0190(87)90038-X</a>"},"publication_status":"published","author":[{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Xiaojun","full_name":"Shen, Xiaojun","last_name":"Shen"}],"abstract":[{"text":"The visibility graph of a finite set of line segments in the plane connects two endpoints u and v if and only if the straight line connection between u and v does not cross any line segment of the set. This article proves that 5n - 4 is a lower bound on the number of edges in the visibility graph of n nonintersecting line segments in the plane. This bound is tight.","lang":"eng"}],"article_processing_charge":"No","publist_id":"2025","volume":26,"date_updated":"2022-02-03T14:05:19Z","oa_version":"None","quality_controlled":"1","acknowledgement":"Research of this author ‘was supported by the Amoco Foundation for Facilitation of Development of Computer\r\nScience under Grant No. l-6-44862.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"issn":["0020-0190"],"eissn":["1872-6119"]},"extern":"1","_id":"4094","doi":"10.1016/0020-0190(87)90038-X","year":"1987","title":"A tight lower bound on the size of visibility graphs","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/002001908790038X?via%3Dihub"}],"type":"journal_article","day":"19","status":"public","intvolume":"        26","page":"61 - 64","publication":"Information Processing Letters","issue":"2","article_type":"original","date_published":"1987-10-19T00:00:00Z","month":"10","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Elsevier","date_created":"2018-12-11T12:06:54Z"},{"author":[{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Mark","last_name":"Overmars","full_name":"Overmars, Mark"}],"abstract":[{"text":"In a number of recent papers, techniques from computational geometry (the field of algorithm design that deals with objects in multi-dimensional space) have been applied to some problems in the area of computer graphics. In this way, efficient solutions were obtained for the windowing problem that asks for those line segments in a planar set that lie in given window (range) and the moving problem that asks for the first line segment that comes into the window when moving the window in some direction. In this paper we show that also the zooming problem, which asks for the first line segment that comes into the window when we enlarge it, can be solved efficiently. This is done by repeatedly performing range queries with ranges of varying sizes. The obtained structure is dynamic and yields a query time of O(log2n) and an insertion and deletion time of O(log2n), where n is the number of line segments in the set. The amount of storage required is O(n log n). It is also shown that the technique of repeated range search can be used to solve several other problems efficiently.","lang":"eng"}],"publication_status":"published","citation":{"apa":"Edelsbrunner, H., &#38; Overmars, M. (1987). Zooming by repeated range detection. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(87)90120-7\">https://doi.org/10.1016/0020-0190(87)90120-7</a>","ieee":"H. Edelsbrunner and M. Overmars, “Zooming by repeated range detection,” <i>Information Processing Letters</i>, vol. 24, no. 6. Elsevier, pp. 413–417, 1987.","chicago":"Edelsbrunner, Herbert, and Mark Overmars. “Zooming by Repeated Range Detection.” <i>Information Processing Letters</i>. Elsevier, 1987. <a href=\"https://doi.org/10.1016/0020-0190(87)90120-7\">https://doi.org/10.1016/0020-0190(87)90120-7</a>.","mla":"Edelsbrunner, Herbert, and Mark Overmars. “Zooming by Repeated Range Detection.” <i>Information Processing Letters</i>, vol. 24, no. 6, Elsevier, 1987, pp. 413–17, doi:<a href=\"https://doi.org/10.1016/0020-0190(87)90120-7\">10.1016/0020-0190(87)90120-7</a>.","ama":"Edelsbrunner H, Overmars M. Zooming by repeated range detection. <i>Information Processing Letters</i>. 1987;24(6):413-417. doi:<a href=\"https://doi.org/10.1016/0020-0190(87)90120-7\">10.1016/0020-0190(87)90120-7</a>","short":"H. Edelsbrunner, M. Overmars, Information Processing Letters 24 (1987) 413–417.","ista":"Edelsbrunner H, Overmars M. 1987. Zooming by repeated range detection. Information Processing Letters. 24(6), 413–417."},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","quality_controlled":"1","_id":"4101","extern":"1","publication_identifier":{"issn":["0020-0190"],"eissn":["1872-6119"]},"date_updated":"2022-02-03T13:29:17Z","volume":24,"publist_id":"2023","article_processing_charge":"No","title":"Zooming by repeated range detection","doi":"10.1016/0020-0190(87)90120-7","year":"1987","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0020019087901207?via%3Dihub"}],"status":"public","intvolume":"        24","type":"journal_article","day":"06","page":"413 - 417","issue":"6","publication":"Information Processing Letters","language":[{"iso":"eng"}],"publisher":"Elsevier","scopus_import":"1","article_type":"original","date_published":"1987-04-06T00:00:00Z","month":"04","date_created":"2018-12-11T12:06:57Z"},{"date_created":"2018-12-11T12:06:56Z","publisher":"Elsevier","language":[{"iso":"eng"}],"month":"11","article_type":"original","date_published":"1986-11-24T00:00:00Z","issue":"5","publication":"Information Processing Letters","page":"289 - 293","intvolume":"        23","status":"public","day":"24","type":"journal_article","title":"Halfplanar range search in linear space and O(n0.695) query time","doi":"10.1016/0020-0190(86)90088-8","year":"1986","_id":"4099","extern":"1","publication_identifier":{"eissn":["1872-6119"],"issn":["0020-0190"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","acknowledgement":"We thank W. Bucher for help in the analysis of the time complexity of the query algorithm. ","quality_controlled":"1","oa_version":"None","date_updated":"2022-02-01T14:17:10Z","volume":23,"publist_id":"2021","article_processing_charge":"No","abstract":[{"text":"Let S denote a set of n points in the Euclidean plane. A halfplanar range query specifies a halfplane h and requires the determination of the number of points in S which are contained in h. A new data structure is described which stores S in O(n) space and allows us to answer a halfplanar range query in O(nlog2(1+√5)−1) time in the worst case, thus improving the best result known before. The structure can be built in O(n log n) time.","lang":"eng"}],"author":[{"first_name":"Herbert","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Welzl, Emo","last_name":"Welzl","first_name":"Emo"}],"publication_status":"published","citation":{"apa":"Edelsbrunner, H., &#38; Welzl, E. (1986). Halfplanar range search in linear space and O(n0.695) query time. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(86)90088-8\">https://doi.org/10.1016/0020-0190(86)90088-8</a>","ieee":"H. Edelsbrunner and E. Welzl, “Halfplanar range search in linear space and O(n0.695) query time,” <i>Information Processing Letters</i>, vol. 23, no. 5. Elsevier, pp. 289–293, 1986.","chicago":"Edelsbrunner, Herbert, and Emo Welzl. “Halfplanar Range Search in Linear Space and O(N0.695) Query Time.” <i>Information Processing Letters</i>. Elsevier, 1986. <a href=\"https://doi.org/10.1016/0020-0190(86)90088-8\">https://doi.org/10.1016/0020-0190(86)90088-8</a>.","ama":"Edelsbrunner H, Welzl E. Halfplanar range search in linear space and O(n0.695) query time. <i>Information Processing Letters</i>. 1986;23(5):289-293. doi:<a href=\"https://doi.org/10.1016/0020-0190(86)90088-8\">10.1016/0020-0190(86)90088-8</a>","mla":"Edelsbrunner, Herbert, and Emo Welzl. “Halfplanar Range Search in Linear Space and O(N0.695) Query Time.” <i>Information Processing Letters</i>, vol. 23, no. 5, Elsevier, 1986, pp. 289–93, doi:<a href=\"https://doi.org/10.1016/0020-0190(86)90088-8\">10.1016/0020-0190(86)90088-8</a>.","ista":"Edelsbrunner H, Welzl E. 1986. Halfplanar range search in linear space and O(n0.695) query time. Information Processing Letters. 23(5), 289–293.","short":"H. Edelsbrunner, E. Welzl, Information Processing Letters 23 (1986) 289–293."}},{"type":"journal_article","day":"10","status":"public","intvolume":"        21","page":"39 - 47","publication":"Information Processing Letters","issue":"1","date_published":"1985-07-10T00:00:00Z","article_type":"original","month":"07","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Elsevier","date_created":"2018-12-11T12:07:00Z","citation":{"ama":"Edelsbrunner H, Maurer H. Finding extreme-points in 3-dimensions and solving the post-office problem in the plane. <i>Information Processing Letters</i>. 1985;21(1):39-47. doi:<a href=\"https://doi.org/10.1016/0020-0190(85)90107-3\">10.1016/0020-0190(85)90107-3</a>","mla":"Edelsbrunner, Herbert, and Hermann Maurer. “Finding Extreme-Points in 3-Dimensions and Solving the Post-Office Problem in the Plane.” <i>Information Processing Letters</i>, vol. 21, no. 1, Elsevier, 1985, pp. 39–47, doi:<a href=\"https://doi.org/10.1016/0020-0190(85)90107-3\">10.1016/0020-0190(85)90107-3</a>.","short":"H. Edelsbrunner, H. Maurer, Information Processing Letters 21 (1985) 39–47.","ista":"Edelsbrunner H, Maurer H. 1985. Finding extreme-points in 3-dimensions and solving the post-office problem in the plane. Information Processing Letters. 21(1), 39–47.","ieee":"H. Edelsbrunner and H. Maurer, “Finding extreme-points in 3-dimensions and solving the post-office problem in the plane,” <i>Information Processing Letters</i>, vol. 21, no. 1. Elsevier, pp. 39–47, 1985.","apa":"Edelsbrunner, H., &#38; Maurer, H. (1985). Finding extreme-points in 3-dimensions and solving the post-office problem in the plane. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(85)90107-3\">https://doi.org/10.1016/0020-0190(85)90107-3</a>","chicago":"Edelsbrunner, Herbert, and Hermann Maurer. “Finding Extreme-Points in 3-Dimensions and Solving the Post-Office Problem in the Plane.” <i>Information Processing Letters</i>. Elsevier, 1985. <a href=\"https://doi.org/10.1016/0020-0190(85)90107-3\">https://doi.org/10.1016/0020-0190(85)90107-3</a>."},"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"},{"first_name":"Hermann","last_name":"Maurer","full_name":"Maurer, Hermann"}],"abstract":[{"text":"This paper describes an optimal solution for the following geometric search problem defined for a set P of n points in three dimensions: Given a plane h with all points of P on one side and a line ℓ in h, determine a point of P that is hit first when h is rotated around ℓ. The solution takes O(n) space and O(log n) time for a query. By use of geometric transforms, the post-office problem for a finite set of points in two dimensions and certain two-dimensional point location problems are reduced to the former problem and thus also optimally solved.","lang":"eng"}],"article_processing_charge":"No","publist_id":"2009","date_updated":"2022-01-31T12:49:12Z","volume":21,"oa_version":"None","quality_controlled":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","acknowledgement":"Research reported in this paper was partially supported by the Austrian Fonds zur Förderung tier wissenschaftlichen\r\nForschung. \r\n","extern":"1","publication_identifier":{"issn":["0020-0190"],"eissn":["1872-6119"]},"_id":"4111","doi":"10.1016/0020-0190(85)90107-3","year":"1985","title":"Finding extreme-points in 3-dimensions and solving the post-office problem in the plane"},{"author":[{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Maurer, Hermann","last_name":"Maurer","first_name":"Hermann"},{"last_name":"Kirkpatrick","full_name":"Kirkpatrick, David","first_name":"David"}],"status":"public","intvolume":"        14","type":"journal_article","day":"20","citation":{"mla":"Edelsbrunner, Herbert, et al. “Polygonal Intersection Searching.” <i>Information Processing Letters</i>, vol. 14, no. 2, Elsevier, 1982, pp. 74–79, doi:<a href=\"https://doi.org/10.1016/0020-0190(82)90090-4\">10.1016/0020-0190(82)90090-4</a>.","ama":"Edelsbrunner H, Maurer H, Kirkpatrick D. Polygonal intersection searching. <i>Information Processing Letters</i>. 1982;14(2):74-79. doi:<a href=\"https://doi.org/10.1016/0020-0190(82)90090-4\">10.1016/0020-0190(82)90090-4</a>","short":"H. Edelsbrunner, H. Maurer, D. Kirkpatrick, Information Processing Letters 14 (1982) 74–79.","ista":"Edelsbrunner H, Maurer H, Kirkpatrick D. 1982. Polygonal intersection searching. Information Processing Letters. 14(2), 74–79.","ieee":"H. Edelsbrunner, H. Maurer, and D. Kirkpatrick, “Polygonal intersection searching,” <i>Information Processing Letters</i>, vol. 14, no. 2. Elsevier, pp. 74–79, 1982.","apa":"Edelsbrunner, H., Maurer, H., &#38; Kirkpatrick, D. (1982). Polygonal intersection searching. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(82)90090-4\">https://doi.org/10.1016/0020-0190(82)90090-4</a>","chicago":"Edelsbrunner, Herbert, Hermann Maurer, and David Kirkpatrick. “Polygonal Intersection Searching.” <i>Information Processing Letters</i>. Elsevier, 1982. <a href=\"https://doi.org/10.1016/0020-0190(82)90090-4\">https://doi.org/10.1016/0020-0190(82)90090-4</a>."},"publication_status":"published","oa_version":"None","quality_controlled":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"issn":["0020-0190"],"eissn":["1872-6119"]},"extern":"1","_id":"4130","article_processing_charge":"No","page":"74 - 79","date_updated":"2022-01-21T11:11:25Z","publist_id":"1991","volume":14,"publication":"Information Processing Letters","issue":"2","language":[{"iso":"eng"}],"title":"Polygonal intersection searching","publisher":"Elsevier","article_type":"original","date_published":"1982-04-20T00:00:00Z","doi":"10.1016/0020-0190(82)90090-4","year":"1982","month":"04","date_created":"2018-12-11T12:07:07Z"},{"quality_controlled":"1","oa_version":"Published Version","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","publication_identifier":{"issn":["0020-0190"]},"extern":"1","_id":"4132","article_processing_charge":"No","volume":13,"date_updated":"2021-12-16T08:38:40Z","publist_id":"1988","oa":1,"author":[{"first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Maurer, Hermann","last_name":"Maurer","first_name":"Hermann"}],"citation":{"apa":"Edelsbrunner, H., &#38; Maurer, H. (1981). On the intersection of Orthogonal objects. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(81)90053-3\">https://doi.org/10.1016/0020-0190(81)90053-3</a>","ieee":"H. Edelsbrunner and H. Maurer, “On the intersection of Orthogonal objects,” <i>Information Processing Letters</i>, vol. 13, no. 4–5. Elsevier, pp. 177–181, 1981.","chicago":"Edelsbrunner, Herbert, and Hermann Maurer. “On the Intersection of Orthogonal Objects.” <i>Information Processing Letters</i>. Elsevier, 1981. <a href=\"https://doi.org/10.1016/0020-0190(81)90053-3\">https://doi.org/10.1016/0020-0190(81)90053-3</a>.","mla":"Edelsbrunner, Herbert, and Hermann Maurer. “On the Intersection of Orthogonal Objects.” <i>Information Processing Letters</i>, vol. 13, no. 4–5, Elsevier, 1981, pp. 177–81, doi:<a href=\"https://doi.org/10.1016/0020-0190(81)90053-3\">10.1016/0020-0190(81)90053-3</a>.","ama":"Edelsbrunner H, Maurer H. On the intersection of Orthogonal objects. <i>Information Processing Letters</i>. 1981;13(4-5):177-181. doi:<a href=\"https://doi.org/10.1016/0020-0190(81)90053-3\">10.1016/0020-0190(81)90053-3</a>","short":"H. Edelsbrunner, H. Maurer, Information Processing Letters 13 (1981) 177–181.","ista":"Edelsbrunner H, Maurer H. 1981. On the intersection of Orthogonal objects. Information Processing Letters. 13(4–5), 177–181."},"publication_status":"published","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0020019081900533","open_access":"1"}],"title":"On the intersection of Orthogonal objects","year":"1981","doi":"10.1016/0020-0190(81)90053-3","page":"177 - 181","publication":"Information Processing Letters","issue":"4-5","status":"public","intvolume":"        13","type":"journal_article","day":"01","date_created":"2018-12-11T12:07:08Z","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Elsevier","date_published":"1981-01-01T00:00:00Z","article_type":"original","month":"01"}]