---
_id: '11759'
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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Paul
  full_name: Dütting, Paul
  last_name: Dütting
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Ingmar
  full_name: Weber, Ingmar
  last_name: Weber
citation:
  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>
  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>
  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>.
  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.
  ista: Dütting P, Henzinger MH, Weber I. 2013. Sponsored search, market equilibria,
    and the Hungarian Method. Information Processing Letters. 113(3), 67–73.
  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>.
  short: P. Dütting, M.H. Henzinger, I. Weber, Information Processing Letters 113
    (2013) 67–73.
date_created: 2022-08-08T11:29:08Z
date_published: 2013-02-15T00:00:00Z
date_updated: 2022-09-12T09:36:15Z
day: '15'
doi: 10.1016/j.ipl.2012.11.006
extern: '1'
external_id:
  arxiv:
  - '0912.1934'
intvolume: '       113'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/0912.1934
month: '02'
oa: 1
oa_version: Preprint
page: 67-73
publication: Information Processing Letters
publication_identifier:
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sponsored search, market equilibria, and the Hungarian Method
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 113
year: '2013'
...
---
_id: '11760'
abstract:
- lang: eng
  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."
article_processing_charge: No
article_type: original
author:
- first_name: Paul
  full_name: Dütting, Paul
  last_name: Dütting
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Ingmar
  full_name: Weber, Ingmar
  last_name: Weber
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>
  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>.
  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.
  ista: Dütting P, Henzinger MH, Weber I. 2011. Offline file assignments for online
    load balancing. Information Processing Letters. 111(4), 178–183.
  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.
date_created: 2022-08-08T11:33:03Z
date_published: 2011-01-15T00:00:00Z
date_updated: 2022-09-12T09:38:05Z
day: '15'
doi: 10.1016/j.ipl.2010.11.022
extern: '1'
intvolume: '       111'
issue: '4'
language:
- iso: eng
month: '01'
oa_version: None
page: 178-183
publication: Information Processing Letters
publication_identifier:
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Offline file assignments for online load balancing
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 111
year: '2011'
...
---
_id: '11761'
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.
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: David P.
  full_name: Williamson, David P.
  last_name: Williamson
citation:
  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>
  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>.
  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.
  ista: Henzinger MH, Williamson DP. 1996. On the number of small cuts in a graph.
    Information Processing Letters. 59(1), 41–44.
  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>.
  short: M.H. Henzinger, D.P. Williamson, Information Processing Letters 59 (1996)
    41–44.
date_created: 2022-08-08T11:49:48Z
date_published: 1996-07-08T00:00:00Z
date_updated: 2022-09-12T09:39:51Z
day: '08'
doi: 10.1016/0020-0190(96)00079-8
extern: '1'
intvolume: '        59'
issue: '1'
language:
- iso: eng
month: '07'
oa_version: None
page: 41-44
publication: Information Processing Letters
publication_identifier:
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the number of small cuts in a graph
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 59
year: '1996'
...
---
_id: '4048'
abstract:
- lang: eng
  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.'
acknowledgement: Research supported by the National Science Foundation under Grant
  CCR-8714565.
article_processing_charge: No
article_type: original
author:
- first_name: Alok
  full_name: Aggarwal, Alok
  last_name: Aggarwal
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Prabhakar
  full_name: Raghavan, Prabhakar
  last_name: Raghavan
- first_name: Prasoon
  full_name: Tiwari, Prasoon
  last_name: Tiwari
citation:
  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>
  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>
  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>.
  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.
  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.
  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>.
  short: A. Aggarwal, H. Edelsbrunner, P. Raghavan, P. Tiwari, Information Processing
    Letters 42 (1992) 55–60.
date_created: 2018-12-11T12:06:38Z
date_published: 1992-04-27T00:00:00Z
date_updated: 2022-03-16T09:20:13Z
day: '27'
doi: 10.1016/0020-0190(92)90133-G
extern: '1'
intvolume: '        42'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/002001909290133G
month: '04'
oa_version: None
page: 55 - 60
publication: Information Processing Letters
publication_identifier:
  eissn:
  - 1872-6119
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '2080'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Optimal time bounds for some proximity problems in the plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 42
year: '1992'
...
---
_id: '4517'
abstract:
- lang: eng
  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.
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. '
article_processing_charge: No
article_type: original
author:
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
citation:
  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>
  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>
  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>.
  ieee: T. A. Henzinger, “Sooner Is Safer Than Later,” <i>Information Processing Letters</i>,
    vol. 43, no. 3. Elsevier, pp. 135–141, 1992.
  ista: Henzinger TA. 1992. Sooner Is Safer Than Later. Information Processing Letters.
    43(3), 135–141.
  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>.
  short: T.A. Henzinger, Information Processing Letters 43 (1992) 135–141.
date_created: 2018-12-11T12:09:16Z
date_published: 1992-09-14T00:00:00Z
date_updated: 2022-03-07T11:31:23Z
day: '14'
doi: 10.1016/0020-0190(92)90005-G
extern: '1'
intvolume: '        43'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/002001909290005G?via%3Dihub
month: '09'
oa_version: None
page: 135 - 141
publication: Information Processing Letters
publication_identifier:
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '211'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sooner Is Safer Than Later
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 43
year: '1992'
...
---
_id: '4094'
abstract:
- lang: eng
  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.
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."
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Xiaojun
  full_name: Shen, Xiaojun
  last_name: Shen
citation:
  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>
  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>
  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.
  ista: Edelsbrunner H, Shen X. 1987. A tight lower bound on the size of visibility
    graphs. Information Processing Letters. 26(2), 61–64.
  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>.
  short: H. Edelsbrunner, X. Shen, Information Processing Letters 26 (1987) 61–64.
date_created: 2018-12-11T12:06:54Z
date_published: 1987-10-19T00:00:00Z
date_updated: 2022-02-03T14:05:19Z
day: '19'
doi: 10.1016/0020-0190(87)90038-X
extern: '1'
intvolume: '        26'
issue: '2'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/002001908790038X?via%3Dihub
month: '10'
oa_version: None
page: 61 - 64
publication: Information Processing Letters
publication_identifier:
  eissn:
  - 1872-6119
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '2025'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A tight lower bound on the size of visibility graphs
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 26
year: '1987'
...
---
_id: '4101'
abstract:
- lang: eng
  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.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Mark
  full_name: Overmars, Mark
  last_name: Overmars
citation:
  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>
  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>
  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>.
  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.
  ista: Edelsbrunner H, Overmars M. 1987. Zooming by repeated range detection. Information
    Processing Letters. 24(6), 413–417.
  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>.
  short: H. Edelsbrunner, M. Overmars, Information Processing Letters 24 (1987) 413–417.
date_created: 2018-12-11T12:06:57Z
date_published: 1987-04-06T00:00:00Z
date_updated: 2022-02-03T13:29:17Z
day: '06'
doi: 10.1016/0020-0190(87)90120-7
extern: '1'
intvolume: '        24'
issue: '6'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0020019087901207?via%3Dihub
month: '04'
oa_version: None
page: 413 - 417
publication: Information Processing Letters
publication_identifier:
  eissn:
  - 1872-6119
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '2023'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Zooming by repeated range detection
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 24
year: '1987'
...
---
_id: '4099'
abstract:
- lang: eng
  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.
acknowledgement: 'We thank W. Bucher for help in the analysis of the time complexity
  of the query algorithm. '
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  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>
  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>
  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>.
  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.
  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.
  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>.
  short: H. Edelsbrunner, E. Welzl, Information Processing Letters 23 (1986) 289–293.
date_created: 2018-12-11T12:06:56Z
date_published: 1986-11-24T00:00:00Z
date_updated: 2022-02-01T14:17:10Z
day: '24'
doi: 10.1016/0020-0190(86)90088-8
extern: '1'
intvolume: '        23'
issue: '5'
language:
- iso: eng
month: '11'
oa_version: None
page: 289 - 293
publication: Information Processing Letters
publication_identifier:
  eissn:
  - 1872-6119
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '2021'
quality_controlled: '1'
status: public
title: Halfplanar range search in linear space and O(n0.695) query time
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 23
year: '1986'
...
---
_id: '4111'
abstract:
- lang: eng
  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.'
acknowledgement: "Research reported in this paper was partially supported by the Austrian
  Fonds zur Förderung tier wissenschaftlichen\r\nForschung. \r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Hermann
  full_name: Maurer, Hermann
  last_name: Maurer
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>
  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>.
  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.
  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.
  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.
date_created: 2018-12-11T12:07:00Z
date_published: 1985-07-10T00:00:00Z
date_updated: 2022-01-31T12:49:12Z
day: '10'
doi: 10.1016/0020-0190(85)90107-3
extern: '1'
intvolume: '        21'
issue: '1'
language:
- iso: eng
month: '07'
oa_version: None
page: 39 - 47
publication: Information Processing Letters
publication_identifier:
  eissn:
  - 1872-6119
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '2009'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Finding extreme-points in 3-dimensions and solving the post-office problem
  in the plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 21
year: '1985'
...
---
_id: '4130'
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Hermann
  full_name: Maurer, Hermann
  last_name: Maurer
- first_name: David
  full_name: Kirkpatrick, David
  last_name: Kirkpatrick
citation:
  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>
  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>.
  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.
  ista: Edelsbrunner H, Maurer H, Kirkpatrick D. 1982. Polygonal intersection searching.
    Information Processing Letters. 14(2), 74–79.
  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>.
  short: H. Edelsbrunner, H. Maurer, D. Kirkpatrick, Information Processing Letters
    14 (1982) 74–79.
date_created: 2018-12-11T12:07:07Z
date_published: 1982-04-20T00:00:00Z
date_updated: 2022-01-21T11:11:25Z
day: '20'
doi: 10.1016/0020-0190(82)90090-4
extern: '1'
intvolume: '        14'
issue: '2'
language:
- iso: eng
month: '04'
oa_version: None
page: 74 - 79
publication: Information Processing Letters
publication_identifier:
  eissn:
  - 1872-6119
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '1991'
quality_controlled: '1'
status: public
title: Polygonal intersection searching
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 14
year: '1982'
...
---
_id: '4132'
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Hermann
  full_name: Maurer, Hermann
  last_name: Maurer
citation:
  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>
  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>
  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>.
  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.
  ista: Edelsbrunner H, Maurer H. 1981. On the intersection of Orthogonal objects.
    Information Processing Letters. 13(4–5), 177–181.
  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>.
  short: H. Edelsbrunner, H. Maurer, Information Processing Letters 13 (1981) 177–181.
date_created: 2018-12-11T12:07:08Z
date_published: 1981-01-01T00:00:00Z
date_updated: 2021-12-16T08:38:40Z
day: '01'
doi: 10.1016/0020-0190(81)90053-3
extern: '1'
intvolume: '        13'
issue: 4-5
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/0020019081900533
month: '01'
oa: 1
oa_version: Published Version
page: 177 - 181
publication: Information Processing Letters
publication_identifier:
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '1988'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the intersection of Orthogonal objects
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 13
year: '1981'
...