---
_id: '4088'
abstract:
- lang: eng
  text: 'Anarrangement ofn lines (or line segments) in the plane is the partition
    of the plane defined by these objects. Such an arrangement consists ofO(n 2) regions,
    calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly,
    using subquadratic space and preprocessing, so that, given any query pointp, we
    can calculate efficiently the face containingp. First, we consider the case of
    lines and show that with (n) space1 and (n 3/2) preprocessing time, we can answer
    face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved
    with high probability.) In the process, we solve three interesting subproblems:
    (1) given a set ofn points, find a straight-edge spanning tree of these points
    such that any line intersects only a few edges of the tree, (2) given a simple
    polygonal path , form a data structure from which we can find the convex hull
    of any subpath of quickly, and (3) given a set of points, organize them so that
    the convex hull of their subset lying above a query line can be found quickly.
    Second, using random sampling, we give a tradeoff between increasing space and
    decreasing query time. Third, we extend our structure to report faces in an arrangement
    of line segments in (n 1/3)+O(K) time, given(n 4/3) space and (n 5/3) preprocessing
    time. Lastly, we note that our techniques allow us to computem faces in an arrangement
    ofn lines in time (m 2/3 n 2/3+n), which is nearly optimal.'
acknowledgement: The first author is pleased to acknowledge the support of Amoco Fnd.
  Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565.
  Work on this paper by the fifth author has been supported by Office of Naval Research
  Grant N00014-87-K-0129, by National Science Foundation Grant 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.
  The sixth author was supported in part by a National Science Foundation Graduate
  Fellowship. This work was begun while the non-DEC authors were visiting at the DEC
  Systems Research Center.
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: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: John
  full_name: Hershberger, John
  last_name: Hershberger
- first_name: Raimund
  full_name: Seidel, Raimund
  last_name: Seidel
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
- first_name: Jack
  full_name: Snoeyink, Jack
  last_name: Snoeyink
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Edelsbrunner H, Guibas L, Hershberger J, et al. Implicitly representing arrangements
    of lines or segments. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):433-466.
    doi:<a href="https://doi.org/10.1007/BF02187742">10.1007/BF02187742</a>
  apa: Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., Sharir, M., Snoeyink,
    J., &#38; Welzl, E. (1989). Implicitly representing arrangements of lines or segments.
    <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187742">https://doi.org/10.1007/BF02187742</a>
  chicago: Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, Raimund Seidel,
    Micha Sharir, Jack Snoeyink, and Emo Welzl. “Implicitly Representing Arrangements
    of Lines or Segments.” <i>Discrete &#38; Computational Geometry</i>. Springer,
    1989. <a href="https://doi.org/10.1007/BF02187742">https://doi.org/10.1007/BF02187742</a>.
  ieee: H. Edelsbrunner <i>et al.</i>, “Implicitly representing arrangements of lines
    or segments,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer,
    pp. 433–466, 1989.
  ista: Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M, Snoeyink J, Welzl
    E. 1989. Implicitly representing arrangements of lines or segments. Discrete &#38;
    Computational Geometry. 4(1), 433–466.
  mla: Edelsbrunner, Herbert, et al. “Implicitly Representing Arrangements of Lines
    or Segments.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer,
    1989, pp. 433–66, doi:<a href="https://doi.org/10.1007/BF02187742">10.1007/BF02187742</a>.
  short: H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink,
    E. Welzl, Discrete &#38; Computational Geometry 4 (1989) 433–466.
date_created: 2018-12-11T12:06:52Z
date_published: 1989-12-01T00:00:00Z
date_updated: 2022-02-10T15:03:48Z
day: '01'
doi: 10.1007/BF02187742
extern: '1'
intvolume: '         4'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://link.springer.com/article/10.1007/BF02187742
month: '12'
oa: 1
oa_version: Published Version
page: 433 - 466
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2036'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Implicitly representing arrangements of lines or segments
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1989'
...
---
_id: '4089'
abstract:
- lang: eng
  text: Motivated by a number of motion-planning questions, we investigate in this
    paper some general topological and combinatorial properties of the boundary of
    the union ofn regions bounded by Jordan curves in the plane. We show that, under
    some fairly weak conditions, a simply connected surface can be constructed that
    exactly covers this union and whose boundary has combinatorial complexity that
    is nearly linear, even though the covered region can have quadratic complexity.
    In the case where our regions are delimited by Jordan acrs in the upper halfplane
    starting and ending on thex-axis such that any pair of arcs intersect in at most
    three points, we prove that the total number of subarcs that appear on the boundary
    of the union is only (n(n)), where(n) is the extremely slowly growing functional
    inverse of Ackermann's function.
acknowledgement: The first author is pleased to acknowledge the support of Amoco Fnd.
  Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565.
  Work on this paper by the fourth and seventh authors has been supported by Office
  of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085,
  and by grants from the Digital Equipment Corporation and the IBM Corporation. The
  seventh author in addition wishes to acknowledge support by a research grant from
  the NCRD—the Israeli National Council for Research and Development. The fifth author
  would like to acknowledge support in part by NSF grant DMS-8501947. Finally, the
  eighth author was supported in part by a National Science Foundation Graduate Fellowship.
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: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: John
  full_name: Hershberger, John
  last_name: Hershberger
- first_name: János
  full_name: Pach, János
  last_name: Pach
- first_name: Richard
  full_name: Pollack, Richard
  last_name: Pollack
- first_name: Raimund
  full_name: Seidel, Raimund
  last_name: Seidel
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
- first_name: Jack
  full_name: Snoeyink, Jack
  last_name: Snoeyink
citation:
  ama: Edelsbrunner H, Guibas L, Hershberger J, et al. On arrangements of Jordan arcs
    with three intersections per pair. <i>Discrete &#38; Computational Geometry</i>.
    1989;4(1):523-539. doi:<a href="https://doi.org/10.1007/BF02187745">10.1007/BF02187745</a>
  apa: Edelsbrunner, H., Guibas, L., Hershberger, J., Pach, J., Pollack, R., Seidel,
    R., … Snoeyink, J. (1989). On arrangements of Jordan arcs with three intersections
    per pair. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187745">https://doi.org/10.1007/BF02187745</a>
  chicago: Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, János Pach, Richard
    Pollack, Raimund Seidel, Micha Sharir, and Jack Snoeyink. “On Arrangements of
    Jordan Arcs with Three Intersections per Pair.” <i>Discrete &#38; Computational
    Geometry</i>. Springer, 1989. <a href="https://doi.org/10.1007/BF02187745">https://doi.org/10.1007/BF02187745</a>.
  ieee: H. Edelsbrunner <i>et al.</i>, “On arrangements of Jordan arcs with three
    intersections per pair,” <i>Discrete &#38; Computational Geometry</i>, vol. 4,
    no. 1. Springer, pp. 523–539, 1989.
  ista: Edelsbrunner H, Guibas L, Hershberger J, Pach J, Pollack R, Seidel R, Sharir
    M, Snoeyink J. 1989. On arrangements of Jordan arcs with three intersections per
    pair. Discrete &#38; Computational Geometry. 4(1), 523–539.
  mla: Edelsbrunner, Herbert, et al. “On Arrangements of Jordan Arcs with Three Intersections
    per Pair.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer,
    1989, pp. 523–39, doi:<a href="https://doi.org/10.1007/BF02187745">10.1007/BF02187745</a>.
  short: H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel,
    M. Sharir, J. Snoeyink, Discrete &#38; Computational Geometry 4 (1989) 523–539.
date_created: 2018-12-11T12:06:52Z
date_published: 1989-12-01T00:00:00Z
date_updated: 2022-02-10T15:40:04Z
day: '01'
doi: 10.1007/BF02187745
extern: '1'
intvolume: '         4'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://link.springer.com/article/10.1007/BF02187745
month: '12'
oa: 1
oa_version: Published Version
page: 523 - 539
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2037'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On arrangements of Jordan arcs with three intersections per pair
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1989'
...
---
_id: '4093'
abstract:
- lang: eng
  text: This paper investigates the combinatorial and computational aspects of certain
    extremal geometric problems in two and three dimensions. Specifically, we examine
    the problem of intersecting a convex subdivision with a line in order to maximize
    the number of intersections. A similar problem is to maximize the number of intersected
    facets in a cross-section of a three-dimensional convex polytope. Related problems
    concern maximum chains in certain families of posets defined over the regions
    of a convex subdivision. In most cases we are able to prove sharp bounds on the
    asymptotic behavior of the corresponding extremal functions. We also describe
    polynomial algorithms for all the problems discussed.
acknowledgement: "Bernard Chazelle wishes to acknowledge the National Science Foundation
  for supporting this research in part under Grant No. MCS83-03925. Herbert Edelsbrunner
  is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862.
  We wish to thank J. Pach and E. Szemeredi for valuable discussions on several\r\nof
  the problems studied in this paper."
article_processing_charge: No
author:
- first_name: Bernard
  full_name: Chazelle, Bernard
  last_name: Chazelle
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
citation:
  ama: Chazelle B, Edelsbrunner H, Guibas L. The complexity of cutting complexes.
    <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):139-181. doi:<a href="https://doi.org/10.1007/BF02187720">10.1007/BF02187720</a>
  apa: Chazelle, B., Edelsbrunner, H., &#38; Guibas, L. (1989). The complexity of
    cutting complexes. <i>Discrete &#38; Computational Geometry</i>. Springer. <a
    href="https://doi.org/10.1007/BF02187720">https://doi.org/10.1007/BF02187720</a>
  chicago: Chazelle, Bernard, Herbert Edelsbrunner, and Leonidas Guibas. “The Complexity
    of Cutting Complexes.” <i>Discrete &#38; Computational Geometry</i>. Springer,
    1989. <a href="https://doi.org/10.1007/BF02187720">https://doi.org/10.1007/BF02187720</a>.
  ieee: B. Chazelle, H. Edelsbrunner, and L. Guibas, “The complexity of cutting complexes,”
    <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 139–181,
    1989.
  ista: Chazelle B, Edelsbrunner H, Guibas L. 1989. The complexity of cutting complexes.
    Discrete &#38; Computational Geometry. 4(1), 139–181.
  mla: Chazelle, Bernard, et al. “The Complexity of Cutting Complexes.” <i>Discrete
    &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 139–81, doi:<a
    href="https://doi.org/10.1007/BF02187720">10.1007/BF02187720</a>.
  short: B. Chazelle, H. Edelsbrunner, L. Guibas, Discrete &#38; Computational Geometry
    4 (1989) 139–181.
date_created: 2018-12-11T12:06:54Z
date_published: 1989-03-01T00:00:00Z
date_updated: 2022-02-10T10:25:57Z
day: '01'
doi: 10.1007/BF02187720
extern: '1'
intvolume: '         4'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187720
month: '03'
oa_version: None
page: 139 - 181
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2032'
quality_controlled: '1'
status: public
title: The complexity of cutting complexes
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1989'
...
---
_id: '4100'
abstract:
- lang: eng
  text: "This paper investigates the existence of linear space data structures for
    range searching. We examine thehomothetic range search problem, where a setS ofn
    points in the plane is to be preprocessed so that for any triangleT with sides
    parallel to three fixed directions the points ofS that lie inT can be computed
    efficiently. We also look atdomination searching in three dimensions. In this
    problem,S is a set ofn points inE 3 and the question is to retrieve all points
    ofS that are dominated by some query point. We describe linear space data structures
    for both problems. The query time is optimal in the first case and nearly optimal
    in the second.\r\n"
acknowledgement: This research was conducted while the first author was with Brown
  University and the second author was with the Technical University of Graz, Austria.
  The first author was supported in part by NSF Grant MCS 83-03925.
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
  full_name: Chazelle, Bernard
  last_name: Chazelle
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  ama: Chazelle B, Edelsbrunner H. Linear space data structures for two types of range
    search. <i>Discrete &#38; Computational Geometry</i>. 1987;2(1):113-126. doi:<a
    href="https://doi.org/10.1007/BF02187875">10.1007/BF02187875</a>
  apa: Chazelle, B., &#38; Edelsbrunner, H. (1987). Linear space data structures for
    two types of range search. <i>Discrete &#38; Computational Geometry</i>. Springer.
    <a href="https://doi.org/10.1007/BF02187875">https://doi.org/10.1007/BF02187875</a>
  chicago: Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures
    for Two Types of Range Search.” <i>Discrete &#38; Computational Geometry</i>.
    Springer, 1987. <a href="https://doi.org/10.1007/BF02187875">https://doi.org/10.1007/BF02187875</a>.
  ieee: B. Chazelle and H. Edelsbrunner, “Linear space data structures for two types
    of range search,” <i>Discrete &#38; Computational Geometry</i>, vol. 2, no. 1.
    Springer, pp. 113–126, 1987.
  ista: Chazelle B, Edelsbrunner H. 1987. Linear space data structures for two types
    of range search. Discrete &#38; Computational Geometry. 2(1), 113–126.
  mla: Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures
    for Two Types of Range Search.” <i>Discrete &#38; Computational Geometry</i>,
    vol. 2, no. 1, Springer, 1987, pp. 113–26, doi:<a href="https://doi.org/10.1007/BF02187875">10.1007/BF02187875</a>.
  short: B. Chazelle, H. Edelsbrunner, Discrete &#38; Computational Geometry 2 (1987)
    113–126.
date_created: 2018-12-11T12:06:56Z
date_published: 1987-01-01T00:00:00Z
date_updated: 2022-02-03T11:07:26Z
day: '01'
doi: 10.1007/BF02187875
extern: '1'
intvolume: '         2'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 113 - 126
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2022'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Linear space data structures for two types of range search
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2
year: '1987'
...
---
_id: '4108'
abstract:
- lang: eng
  text: We propose a uniform and general framework for defining and dealing with Voronoi
    diagrams. In this framework a Voronoi diagram is a partition of a domainD induced
    by a finite number of real valued functions onD. Valuable insight can be gained
    when one considers how these real valued functions partitionD ×R. With this view
    it turns out that the standard Euclidean Voronoi diagram of point sets inR d along
    with its order-k generalizations are intimately related to certain arrangements
    of hyperplanes. This fact can be used to obtain new Voronoi diagram algorithms.
    We also discuss how the formalism of arrangements can be used to solve certain
    intersection and union problems.
acknowledgement: 'We would like to thank John Gilbert for his careful reading of the
  manuscript and his many suggestions for improvement. We also want to thank Bennett
  Battaile, Gianfranco Bilardi, Joseph O''Rourke, and Chee Yap for their comments. '
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: Raimund
  full_name: Seidel, Raimund
  last_name: Seidel
citation:
  ama: Edelsbrunner H, Seidel R. Voronoi diagrams and arrangements. <i>Discrete &#38;
    Computational Geometry</i>. 1986;1(1):25-44. doi:<a href="https://doi.org/10.1007/BF02187681">10.1007/BF02187681</a>
  apa: Edelsbrunner, H., &#38; Seidel, R. (1986). Voronoi diagrams and arrangements.
    <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187681">https://doi.org/10.1007/BF02187681</a>
  chicago: Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.”
    <i>Discrete &#38; Computational Geometry</i>. Springer, 1986. <a href="https://doi.org/10.1007/BF02187681">https://doi.org/10.1007/BF02187681</a>.
  ieee: H. Edelsbrunner and R. Seidel, “Voronoi diagrams and arrangements,” <i>Discrete
    &#38; Computational Geometry</i>, vol. 1, no. 1. Springer, pp. 25–44, 1986.
  ista: Edelsbrunner H, Seidel R. 1986. Voronoi diagrams and arrangements. Discrete
    &#38; Computational Geometry. 1(1), 25–44.
  mla: Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.”
    <i>Discrete &#38; Computational Geometry</i>, vol. 1, no. 1, Springer, 1986, pp.
    25–44, doi:<a href="https://doi.org/10.1007/BF02187681">10.1007/BF02187681</a>.
  short: H. Edelsbrunner, R. Seidel, Discrete &#38; Computational Geometry 1 (1986)
    25–44.
date_created: 2018-12-11T12:06:59Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T08:53:39Z
day: '01'
doi: 10.1007/BF02187681
extern: '1'
intvolume: '         1'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 25 - 44
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2012'
quality_controlled: '1'
status: public
title: Voronoi diagrams and arrangements
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1986'
...