---
_id: '2419'
abstract:
- lang: eng
  text: For an absolutely continuous probability measure μ. on ℝd and a nonnegative
    integer k, let S̃k(μ, 0) denote the probability that the convex hull of k + d
    + 1 random points which are i.i.d. according to μ contains the origin 0. For d
    and k given, we determine a tight upper bound on S̃k(μ, 0), and we characterize
    the measures in ℝd which attain this bound. As we will see, this result can be
    considered a continuous analogue of the Upper Bound Theorem for the maximal number
    of faces of convex polytopes with a given number of vertices. For our proof we
    introduce so-called h-functions, continuous counterparts of h-vectors of simplicial
    convex polytopes.
acknowledgement: We are indebted to Rolf Schneider for many helpful remarks and in
  particular for bringing reference [6] to our attention
article_processing_charge: No
article_type: original
author:
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Wagner U, Welzl E. A continuous analogue of the Upper Bound Theorem. <i>Discrete
    &#38; Computational Geometry</i>. 2001;26(2):205-219. doi:<a href="https://doi.org/10.1007/s00454-001-0028-9">10.1007/s00454-001-0028-9</a>
  apa: Wagner, U., &#38; Welzl, E. (2001). A continuous analogue of the Upper Bound
    Theorem. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/s00454-001-0028-9">https://doi.org/10.1007/s00454-001-0028-9</a>
  chicago: Wagner, Uli, and Emo Welzl. “A Continuous Analogue of the Upper Bound Theorem.”
    <i>Discrete &#38; Computational Geometry</i>. Springer, 2001. <a href="https://doi.org/10.1007/s00454-001-0028-9">https://doi.org/10.1007/s00454-001-0028-9</a>.
  ieee: U. Wagner and E. Welzl, “A continuous analogue of the Upper Bound Theorem,”
    <i>Discrete &#38; Computational Geometry</i>, vol. 26, no. 2. Springer, pp. 205–219,
    2001.
  ista: Wagner U, Welzl E. 2001. A continuous analogue of the Upper Bound Theorem.
    Discrete &#38; Computational Geometry. 26(2), 205–219.
  mla: Wagner, Uli, and Emo Welzl. “A Continuous Analogue of the Upper Bound Theorem.”
    <i>Discrete &#38; Computational Geometry</i>, vol. 26, no. 2, Springer, 2001,
    pp. 205–19, doi:<a href="https://doi.org/10.1007/s00454-001-0028-9">10.1007/s00454-001-0028-9</a>.
  short: U. Wagner, E. Welzl, Discrete &#38; Computational Geometry 26 (2001) 205–219.
date_created: 2018-12-11T11:57:33Z
date_published: 2001-01-01T00:00:00Z
date_updated: 2023-05-24T13:13:51Z
day: '01'
doi: 10.1007/s00454-001-0028-9
extern: '1'
intvolume: '        26'
issue: '2'
language:
- iso: eng
month: '01'
oa_version: None
page: 205 - 219
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '4506'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A continuous analogue of the Upper Bound Theorem
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 26
year: '2001'
...
---
_id: '4007'
abstract:
- lang: eng
  text: 'This paper describes an algorithm for maintaining an approximating triangulation
    of a deforming surface in R 3 . The surface is the envelope of an infinite family
    of spheres defined and controlled by a finite collection of weighted points. The
    triangulation adapts dynamically to changing shape, curvature, and topology of
    the surface. '
acknowledgement: NSF under grant DMS- 98-73945, ARO under grant DAAG55-98-1-0177,
  NSF under grants CCR-96- 19542 and CCR-97-12088.
article_processing_charge: No
article_type: original
author:
- first_name: Ho
  full_name: Cheng, Ho
  last_name: Cheng
- first_name: Tamal
  full_name: Dey, Tamal
  last_name: Dey
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: John
  full_name: Sullivan, John
  last_name: Sullivan
citation:
  ama: Cheng H, Dey T, Edelsbrunner H, Sullivan J. Dynamic skin triangulation. <i>Discrete
    &#38; Computational Geometry</i>. 2001;25(4):525-568. doi:<a href="https://doi.org/10.1007/s00454-001-0007-1">10.1007/s00454-001-0007-1</a>
  apa: Cheng, H., Dey, T., Edelsbrunner, H., &#38; Sullivan, J. (2001). Dynamic skin
    triangulation. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/s00454-001-0007-1">https://doi.org/10.1007/s00454-001-0007-1</a>
  chicago: Cheng, Ho, Tamal Dey, Herbert Edelsbrunner, and John Sullivan. “Dynamic
    Skin Triangulation.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2001.
    <a href="https://doi.org/10.1007/s00454-001-0007-1">https://doi.org/10.1007/s00454-001-0007-1</a>.
  ieee: H. Cheng, T. Dey, H. Edelsbrunner, and J. Sullivan, “Dynamic skin triangulation,”
    <i>Discrete &#38; Computational Geometry</i>, vol. 25, no. 4. Springer, pp. 525–568,
    2001.
  ista: Cheng H, Dey T, Edelsbrunner H, Sullivan J. 2001. Dynamic skin triangulation.
    Discrete &#38; Computational Geometry. 25(4), 525–568.
  mla: Cheng, Ho, et al. “Dynamic Skin Triangulation.” <i>Discrete &#38; Computational
    Geometry</i>, vol. 25, no. 4, Springer, 2001, pp. 525–68, doi:<a href="https://doi.org/10.1007/s00454-001-0007-1">10.1007/s00454-001-0007-1</a>.
  short: H. Cheng, T. Dey, H. Edelsbrunner, J. Sullivan, Discrete &#38; Computational
    Geometry 25 (2001) 525–568.
date_created: 2018-12-11T12:06:24Z
date_published: 2001-04-04T00:00:00Z
date_updated: 2023-05-10T12:45:59Z
day: '04'
doi: 10.1007/s00454-001-0007-1
extern: '1'
intvolume: '        25'
issue: '4'
language:
- iso: eng
month: '04'
oa_version: None
page: 525 - 568
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2122'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic skin triangulation
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 25
year: '2001'
...
---
_id: '4004'
abstract:
- lang: eng
  text: In this paper we introduce the abacus model of a simplex and use it to subdivide
    a d-simplex into k(d) d-simplices all of the same volume and shape characteristics.
    The construction is an extension of the subdivision method of Freudenthal [3]
    and has been used by Goodman and Peters [4] to design smooth manifolds.
acknowledgement: NSF under Grant DMS 98-73945, NSF under Grant CCR-96-19542 and by
  ARO under Grant DAAG55- 98-1-0177.
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: Daniel
  full_name: Grayson, Daniel
  last_name: Grayson
citation:
  ama: Edelsbrunner H, Grayson D. Edgewise subdivision of a simplex. <i>Discrete &#38;
    Computational Geometry</i>. 2000;24(4):707-719. doi:<a href="https://doi.org/10.1007/s004540010063">10.1007/s004540010063</a>
  apa: Edelsbrunner, H., &#38; Grayson, D. (2000). Edgewise subdivision of a simplex.
    <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/s004540010063">https://doi.org/10.1007/s004540010063</a>
  chicago: Edelsbrunner, Herbert, and Daniel Grayson. “Edgewise Subdivision of a Simplex.”
    <i>Discrete &#38; Computational Geometry</i>. Springer, 2000. <a href="https://doi.org/10.1007/s004540010063">https://doi.org/10.1007/s004540010063</a>.
  ieee: H. Edelsbrunner and D. Grayson, “Edgewise subdivision of a simplex,” <i>Discrete
    &#38; Computational Geometry</i>, vol. 24, no. 4. Springer, pp. 707–719, 2000.
  ista: Edelsbrunner H, Grayson D. 2000. Edgewise subdivision of a simplex. Discrete
    &#38; Computational Geometry. 24(4), 707–719.
  mla: Edelsbrunner, Herbert, and Daniel Grayson. “Edgewise Subdivision of a Simplex.”
    <i>Discrete &#38; Computational Geometry</i>, vol. 24, no. 4, Springer, 2000,
    pp. 707–19, doi:<a href="https://doi.org/10.1007/s004540010063">10.1007/s004540010063</a>.
  short: H. Edelsbrunner, D. Grayson, Discrete &#38; Computational Geometry 24 (2000)
    707–719.
date_created: 2018-12-11T12:06:23Z
date_published: 2000-12-01T00:00:00Z
date_updated: 2023-05-02T11:43:59Z
day: '01'
doi: 10.1007/s004540010063
extern: '1'
intvolume: '        24'
issue: '4'
language:
- iso: eng
month: '12'
oa_version: None
page: 707 - 719
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2119'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Edgewise subdivision of a simplex
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 24
year: '2000'
...
---
_id: '4014'
abstract:
- lang: eng
  text: A new paradigm for designing smooth surfaces is described. A finite set of
    points with weights specifies a closed surface in space referred to as skin. It
    consists of one or more components, each tangent continuous and free of self-intersections
    and intersections with other components. The skin varies continuously with the
    weights and locations of the points, and the variation includes the possibility
    of a topology change facilitated by the violation of tangent continuity at a single
    point in space and time. Applications of the skin to molecular modeling and to
    geometric deformation are discussed.
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
citation:
  ama: Edelsbrunner H. Deformable smooth surface design. <i>Discrete &#38; Computational
    Geometry</i>. 1999;21(1):87-115. doi:<a href="https://doi.org/10.1007/PL00009412">10.1007/PL00009412</a>
  apa: Edelsbrunner, H. (1999). Deformable smooth surface design. <i>Discrete &#38;
    Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/PL00009412">https://doi.org/10.1007/PL00009412</a>
  chicago: Edelsbrunner, Herbert. “Deformable Smooth Surface Design.” <i>Discrete
    &#38; Computational Geometry</i>. Springer, 1999. <a href="https://doi.org/10.1007/PL00009412">https://doi.org/10.1007/PL00009412</a>.
  ieee: H. Edelsbrunner, “Deformable smooth surface design,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 21, no. 1. Springer, pp. 87–115, 1999.
  ista: Edelsbrunner H. 1999. Deformable smooth surface design. Discrete &#38; Computational
    Geometry. 21(1), 87–115.
  mla: Edelsbrunner, Herbert. “Deformable Smooth Surface Design.” <i>Discrete &#38;
    Computational Geometry</i>, vol. 21, no. 1, Springer, 1999, pp. 87–115, doi:<a
    href="https://doi.org/10.1007/PL00009412">10.1007/PL00009412</a>.
  short: H. Edelsbrunner, Discrete &#38; Computational Geometry 21 (1999) 87–115.
date_created: 2018-12-11T12:06:26Z
date_published: 1999-01-01T00:00:00Z
date_updated: 2022-09-06T09:02:23Z
day: '01'
doi: 10.1007/PL00009412
extern: '1'
intvolume: '        21'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 87 - 115
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2115'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deformable smooth surface design
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 21
year: '1999'
...
---
_id: '4022'
abstract:
- lang: eng
  text: A halving hyperplane of a set S of n points in R(d) contains d affinely independent
    points of S so that equally many of the points off the hyperplane lie in each
    of the two half-spaces. We prove bounds on the number of halving hyperplanes under
    the condition that the ratio of largest over smallest distance between any two
    points is at most delta n(1/d), delta some constant. Such a set S is called dense.
    In d = 2 dimensions the number of halving lines for a dense set can be as much
    as Omega(n log n), and it cannot exceed O (n(5/4)/log* n). The upper bound improves
    over the current best bound of O (n(3/2)/log* n) which holds more generally without
    any density assumption. In d = 3 dimensions we show that O (n(7/3)) is an upper
    bound on the number of halving planes for a dense set, The proof is based on a
    metric argument that can be extended to d greater than or equal to 4 dimensions,
    where it leads to O (n(d-2/d)) as an upper bound for the number of halving hyperplanes.
acknowledgement: Partially supported by the National Science Foundation, under Grant
  ASC-9200301 and the Alan T. Waterman award, Grant CCR-9118874.
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: Pavel
  full_name: Valtr, Pavel
  last_name: Valtr
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Edelsbrunner H, Valtr P, Welzl E. Cutting dense point sets in half. <i>Discrete
    &#38; Computational Geometry</i>. 1997;17(3):243-255. doi:<a href="https://doi.org/10.1007/PL00009291">10.1007/PL00009291</a>
  apa: Edelsbrunner, H., Valtr, P., &#38; Welzl, E. (1997). Cutting dense point sets
    in half. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/PL00009291">https://doi.org/10.1007/PL00009291</a>
  chicago: Edelsbrunner, Herbert, Pavel Valtr, and Emo Welzl. “Cutting Dense Point
    Sets in Half.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1997. <a
    href="https://doi.org/10.1007/PL00009291">https://doi.org/10.1007/PL00009291</a>.
  ieee: H. Edelsbrunner, P. Valtr, and E. Welzl, “Cutting dense point sets in half,”
    <i>Discrete &#38; Computational Geometry</i>, vol. 17, no. 3. Springer, pp. 243–255,
    1997.
  ista: Edelsbrunner H, Valtr P, Welzl E. 1997. Cutting dense point sets in half.
    Discrete &#38; Computational Geometry. 17(3), 243–255.
  mla: Edelsbrunner, Herbert, et al. “Cutting Dense Point Sets in Half.” <i>Discrete
    &#38; Computational Geometry</i>, vol. 17, no. 3, Springer, 1997, pp. 243–55,
    doi:<a href="https://doi.org/10.1007/PL00009291">10.1007/PL00009291</a>.
  short: H. Edelsbrunner, P. Valtr, E. Welzl, Discrete &#38; Computational Geometry
    17 (1997) 243–255.
date_created: 2018-12-11T12:06:29Z
date_published: 1997-04-01T00:00:00Z
date_updated: 2022-08-18T14:08:38Z
day: '01'
doi: 10.1007/PL00009291
extern: '1'
intvolume: '        17'
issue: '3'
language:
- iso: eng
month: '04'
oa_version: None
page: 243 - 255
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2103'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Cutting dense point sets in half
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 17
year: '1997'
...
---
_id: '4023'
abstract:
- lang: eng
  text: Let B be a finite pseudodisk collection in the plane. By the principle of
    inclusion-exclusion, the area or any other measure of the union is [GRAPHICS]
    We show the existence of a two-dimensional abstract simplicial complex, X subset
    of or equal to 2(B), so the above relation holds even if X is substituted for
    2(B). In addition, X can be embedded in R(2) SO its underlying space is homotopy
    equivalent to int Boolean OR B, and the frontier of X is isomorphic to the nerve
    of the set of boundary contributions.
acknowledgement: Supported by the National Science Foundation, under Grant ASC-9200301
  and the Alan T. Waterman Award CCR-9118874.
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: Edgar
  full_name: Ramos, Edgar
  last_name: Ramos
citation:
  ama: Edelsbrunner H, Ramos E. Inclusion-exclusion complexes for pseudodisk collections.
    <i>Discrete &#38; Computational Geometry</i>. 1997;17(3):287-306. doi:<a href="https://doi.org/10.1007/PL00009295">10.1007/PL00009295</a>
  apa: Edelsbrunner, H., &#38; Ramos, E. (1997). Inclusion-exclusion complexes for
    pseudodisk collections. <i>Discrete &#38; Computational Geometry</i>. Springer.
    <a href="https://doi.org/10.1007/PL00009295">https://doi.org/10.1007/PL00009295</a>
  chicago: Edelsbrunner, Herbert, and Edgar Ramos. “Inclusion-Exclusion Complexes
    for Pseudodisk Collections.” <i>Discrete &#38; Computational Geometry</i>. Springer,
    1997. <a href="https://doi.org/10.1007/PL00009295">https://doi.org/10.1007/PL00009295</a>.
  ieee: H. Edelsbrunner and E. Ramos, “Inclusion-exclusion complexes for pseudodisk
    collections,” <i>Discrete &#38; Computational Geometry</i>, vol. 17, no. 3. Springer,
    pp. 287–306, 1997.
  ista: Edelsbrunner H, Ramos E. 1997. Inclusion-exclusion complexes for pseudodisk
    collections. Discrete &#38; Computational Geometry. 17(3), 287–306.
  mla: Edelsbrunner, Herbert, and Edgar Ramos. “Inclusion-Exclusion Complexes for
    Pseudodisk Collections.” <i>Discrete &#38; Computational Geometry</i>, vol. 17,
    no. 3, Springer, 1997, pp. 287–306, doi:<a href="https://doi.org/10.1007/PL00009295">10.1007/PL00009295</a>.
  short: H. Edelsbrunner, E. Ramos, Discrete &#38; Computational Geometry 17 (1997)
    287–306.
date_created: 2018-12-11T12:06:30Z
date_published: 1997-04-01T00:00:00Z
date_updated: 2022-08-18T14:39:39Z
day: '01'
doi: 10.1007/PL00009295
extern: '1'
intvolume: '        17'
issue: '3'
language:
- iso: eng
month: '04'
oa_version: None
page: 287 - 306
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2104'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Inclusion-exclusion complexes for pseudodisk collections
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 17
year: '1997'
...
---
_id: '4028'
abstract:
- lang: eng
  text: Efficient algorithms are described for computing topological, combinatorial,
    and metric properties of the union of finitely many spherical balls in R(d) These
    algorithms are based on a simplicial complex dual to a decomposition of the union
    of balls using Voronoi cells, and on short inclusion-exclusion formulas derived
    from this complex. The algorithms are most relevant in R(3) where unions of finitely
    many balls are commonly used as models of molecules.
acknowledgement: This work is supported by the National Science Foundation, under
  Grant ASC-9200301, and the Alan T. Waterman award, Grant CCR-9118874. Any opinions,
  findings, conclusions, or recommendations expressed in this publication are those
  of the author and do not necessarily reflect the view of the National Science Foundation.
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
citation:
  ama: Edelsbrunner H. The union of balls and its dual shape. <i>Discrete &#38; Computational
    Geometry</i>. 1995;13(1):415-440. doi:<a href="https://doi.org/10.1007/BF02574053">10.1007/BF02574053</a>
  apa: Edelsbrunner, H. (1995). The union of balls and its dual shape. <i>Discrete
    &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02574053">https://doi.org/10.1007/BF02574053</a>
  chicago: Edelsbrunner, Herbert. “The Union of Balls and Its Dual Shape.” <i>Discrete
    &#38; Computational Geometry</i>. Springer, 1995. <a href="https://doi.org/10.1007/BF02574053">https://doi.org/10.1007/BF02574053</a>.
  ieee: H. Edelsbrunner, “The union of balls and its dual shape,” <i>Discrete &#38;
    Computational Geometry</i>, vol. 13, no. 1. Springer, pp. 415–440, 1995.
  ista: Edelsbrunner H. 1995. The union of balls and its dual shape. Discrete &#38;
    Computational Geometry. 13(1), 415–440.
  mla: Edelsbrunner, Herbert. “The Union of Balls and Its Dual Shape.” <i>Discrete
    &#38; Computational Geometry</i>, vol. 13, no. 1, Springer, 1995, pp. 415–40,
    doi:<a href="https://doi.org/10.1007/BF02574053">10.1007/BF02574053</a>.
  short: H. Edelsbrunner, Discrete &#38; Computational Geometry 13 (1995) 415–440.
date_created: 2018-12-11T12:06:31Z
date_published: 1995-12-01T00:00:00Z
date_updated: 2022-06-27T08:14:48Z
day: '01'
doi: 10.1007/BF02574053
extern: '1'
intvolume: '        13'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://link.springer.com/article/10.1007/BF02574053
month: '12'
oa: 1
oa_version: Published Version
page: 415 - 440
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2095'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The union of balls and its dual shape
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 13
year: '1995'
...
---
_id: '4035'
abstract:
- lang: eng
  text: 'Let S be a set of n points in ℝd . A set W is a weak ε-net for (convex ranges
    of)S if, for any T⊆S containing εn points, the convex hull of T intersects W.
    We show the existence of weak ε-nets of size {Mathematical expression}, where
    β2=0, β3=1, and βd ≈0.149·2d-1(d-1)!, improving a previous bound of Alon et al.
    Such a net can be computed effectively. We also consider two special cases: when
    S is a planar point set in convex position, we prove the existence of a net of
    size O((1/ε) log1.6(1/ε)). In the case where S consists of the vertices of a regular
    polygon, we use an argument from hyperbolic geometry to exhibit an optimal net
    of size O(1/ε), which improves a previous bound of Capoyleas.'
acknowledgement: The authors wish to express their gratitude for the support and hospitality
  of the DEC Palo Alto Systems Research Center.
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
- first_name: Michelangelo
  full_name: Grigni, Michelangelo
  last_name: Grigni
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Sharir M, Welzl E. Improved
    bounds on weak ε-nets for convex sets. <i>Discrete &#38; Computational Geometry</i>.
    1995;13(1):1-15. doi:<a href="https://doi.org/10.1007/BF02574025">10.1007/BF02574025</a>
  apa: Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Sharir, M., &#38; Welzl,
    E. (1995). Improved bounds on weak ε-nets for convex sets. <i>Discrete &#38; Computational
    Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02574025">https://doi.org/10.1007/BF02574025</a>
  chicago: Chazelle, Bernard, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas
    Guibas, Micha Sharir, and Emo Welzl. “Improved Bounds on Weak ε-Nets for Convex
    Sets.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1995. <a href="https://doi.org/10.1007/BF02574025">https://doi.org/10.1007/BF02574025</a>.
  ieee: B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, and E. Welzl,
    “Improved bounds on weak ε-nets for convex sets,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 13, no. 1. Springer, pp. 1–15, 1995.
  ista: Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Sharir M, Welzl E. 1995. Improved
    bounds on weak ε-nets for convex sets. Discrete &#38; Computational Geometry.
    13(1), 1–15.
  mla: Chazelle, Bernard, et al. “Improved Bounds on Weak ε-Nets for Convex Sets.”
    <i>Discrete &#38; Computational Geometry</i>, vol. 13, no. 1, Springer, 1995,
    pp. 1–15, doi:<a href="https://doi.org/10.1007/BF02574025">10.1007/BF02574025</a>.
  short: B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, E. Welzl,
    Discrete &#38; Computational Geometry 13 (1995) 1–15.
date_created: 2018-12-11T12:06:33Z
date_published: 1995-12-01T00:00:00Z
date_updated: 2022-06-13T12:37:06Z
day: '01'
doi: 10.1007/BF02574025
extern: '1'
intvolume: '        13'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02574025
month: '12'
oa_version: None
page: 1 - 15
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2094'
quality_controlled: '1'
status: public
title: Improved bounds on weak ε-nets for convex sets
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 13
year: '1995'
...
---
_id: '4032'
abstract:
- lang: eng
  text: Every collection of t≥2 n2 triangles with a total of n vertices in ℝ3 has
    Ω(t4/n6) crossing pairs. This implies that one of their edges meets Ω(t3/n6) of
    the triangles. From this it follows that n points in ℝ3 have only O(n8/3) halving
    planes.
acknowledgement: The research of H. Edelsbrunner was supported by the National Science
  Foundation under Grant CCR-8921421 and under an Alan T. Waterman award, Grant CCR-9118874.
  Any opinions, findings and conclusions or recommendations expressed in this publication
  are those of the authors and do not necessarily reflect the view of the National
  Science Foundation.
article_processing_charge: No
article_type: original
author:
- first_name: Tamal
  full_name: Dey, Tamal
  last_name: Dey
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  ama: Dey T, Edelsbrunner H. Counting triangle crossings and halving planes. <i>Discrete
    &#38; Computational Geometry</i>. 1994;12(1):281-289. doi:<a href="https://doi.org/10.1007/BF02574381">10.1007/BF02574381</a>
  apa: Dey, T., &#38; Edelsbrunner, H. (1994). Counting triangle crossings and halving
    planes. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02574381">https://doi.org/10.1007/BF02574381</a>
  chicago: Dey, Tamal, and Herbert Edelsbrunner. “Counting Triangle Crossings and
    Halving Planes.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1994.
    <a href="https://doi.org/10.1007/BF02574381">https://doi.org/10.1007/BF02574381</a>.
  ieee: T. Dey and H. Edelsbrunner, “Counting triangle crossings and halving planes,”
    <i>Discrete &#38; Computational Geometry</i>, vol. 12, no. 1. Springer, pp. 281–289,
    1994.
  ista: Dey T, Edelsbrunner H. 1994. Counting triangle crossings and halving planes.
    Discrete &#38; Computational Geometry. 12(1), 281–289.
  mla: Dey, Tamal, and Herbert Edelsbrunner. “Counting Triangle Crossings and Halving
    Planes.” <i>Discrete &#38; Computational Geometry</i>, vol. 12, no. 1, Springer,
    1994, pp. 281–89, doi:<a href="https://doi.org/10.1007/BF02574381">10.1007/BF02574381</a>.
  short: T. Dey, H. Edelsbrunner, Discrete &#38; Computational Geometry 12 (1994)
    281–289.
date_created: 2018-12-11T12:06:33Z
date_published: 1994-09-01T00:00:00Z
date_updated: 2022-06-02T12:53:01Z
day: '01'
doi: 10.1007/BF02574381
extern: '1'
intvolume: '        12'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02574381
month: '09'
oa_version: None
page: 281 - 289
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2091'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counting triangle crossings and halving planes
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 12
year: '1994'
...
---
_id: '4040'
abstract:
- lang: eng
  text: A plane geometric graph C in ℝ2 conforms to another such graph G if each edge
    of G is the union of some edges of C. It is proved that, for every G with n vertices
    and m edges, there is a completion of a Delaunay triangulation of O(m2 n) points
    that conforms to G. The algorithm that constructs the points is also described.
acknowledgement: 'Research of the first author is supported by the National Science
  Foundation under Grant CCR-8921421 and under the Alan T. Waterman award, Grant CCR-9118874.
  Any opinions, findings, and conclusions or recommendations expressed in this publication
  are those of the authors and do not necessarily reflect the view of the National
  Science Foundation. Work of the second author was conducted while he was on study
  leave at the University of Illinois. '
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: Tiow
  full_name: Tan, Tiow
  last_name: Tan
citation:
  ama: Edelsbrunner H, Tan T. An upper bound for conforming Delaunay triangulations.
    <i>Discrete &#38; Computational Geometry</i>. 1993;10(1):197-213. doi:<a href="https://doi.org/10.1007/BF02573974">10.1007/BF02573974</a>
  apa: Edelsbrunner, H., &#38; Tan, T. (1993). An upper bound for conforming Delaunay
    triangulations. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02573974">https://doi.org/10.1007/BF02573974</a>
  chicago: Edelsbrunner, Herbert, and Tiow Tan. “An Upper Bound for Conforming Delaunay
    Triangulations.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1993.
    <a href="https://doi.org/10.1007/BF02573974">https://doi.org/10.1007/BF02573974</a>.
  ieee: H. Edelsbrunner and T. Tan, “An upper bound for conforming Delaunay triangulations,”
    <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1. Springer, pp. 197–213,
    1993.
  ista: Edelsbrunner H, Tan T. 1993. An upper bound for conforming Delaunay triangulations.
    Discrete &#38; Computational Geometry. 10(1), 197–213.
  mla: Edelsbrunner, Herbert, and Tiow Tan. “An Upper Bound for Conforming Delaunay
    Triangulations.” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1,
    Springer, 1993, pp. 197–213, doi:<a href="https://doi.org/10.1007/BF02573974">10.1007/BF02573974</a>.
  short: H. Edelsbrunner, T. Tan, Discrete &#38; Computational Geometry 10 (1993)
    197–213.
date_created: 2018-12-11T12:06:35Z
date_published: 1993-12-01T00:00:00Z
date_updated: 2022-03-28T14:58:16Z
day: '01'
doi: 10.1007/BF02573974
extern: '1'
intvolume: '        10'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02573974
month: '12'
oa_version: None
page: 197 - 213
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2084'
quality_controlled: '1'
status: public
title: An upper bound for conforming Delaunay triangulations
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 10
year: '1993'
...
---
_id: '4044'
abstract:
- lang: eng
  text: Edge insertion iteratively improves a triangulation of a finite point set
    in ℜ2 by adding a new edge, deleting old edges crossing the new edge, and retriangulating
    the polygonal regions on either side of the new edge. This paper presents an abstract
    view of the edge insertion paradigm, and then shows that it gives polynomial-time
    algorithms for several types of optimal triangulations, including minimizing the
    maximum slope of a piecewise-linear interpolating surface.
acknowledgement: "The authors thank two anonymous referees for suggestions on improving
  the style of this paper. The research of the second' author was supported by the
  National Science Foundation under Grant No. CCR-8921421 and under the Alan T. Waterman
  award, Grant No. CCR-9118874. Any opinions, findings, and conclusions or recommendations
  expressed in this publication are those of the authors and do not necessarily reflect
  the view of the National Science Foundation. Part of the work was done while the
  second, third, and fourth authors visited the Xerox Palo Alto Research Center,\r\nand
  while the fifth author was on study leave at the University of Illinois. "
article_processing_charge: No
article_type: original
author:
- first_name: Marshall
  full_name: Bern, Marshall
  last_name: Bern
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: David
  full_name: Eppstein, David
  last_name: Eppstein
- first_name: Stephen
  full_name: Mitchell, Stephen
  last_name: Mitchell
- first_name: Tiow
  full_name: Tan, Tiow
  last_name: Tan
citation:
  ama: Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. Edge insertion for optimal
    triangulations. <i>Discrete &#38; Computational Geometry</i>. 1993;10(1):47-65.
    doi:<a href="https://doi.org/10.1007/BF02573962">10.1007/BF02573962</a>
  apa: Bern, M., Edelsbrunner, H., Eppstein, D., Mitchell, S., &#38; Tan, T. (1993).
    Edge insertion for optimal triangulations. <i>Discrete &#38; Computational Geometry</i>.
    Springer. <a href="https://doi.org/10.1007/BF02573962">https://doi.org/10.1007/BF02573962</a>
  chicago: Bern, Marshall, Herbert Edelsbrunner, David Eppstein, Stephen Mitchell,
    and Tiow Tan. “Edge Insertion for Optimal Triangulations.” <i>Discrete &#38; Computational
    Geometry</i>. Springer, 1993. <a href="https://doi.org/10.1007/BF02573962">https://doi.org/10.1007/BF02573962</a>.
  ieee: M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, and T. Tan, “Edge insertion
    for optimal triangulations,” <i>Discrete &#38; Computational Geometry</i>, vol.
    10, no. 1. Springer, pp. 47–65, 1993.
  ista: Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. 1993. Edge insertion
    for optimal triangulations. Discrete &#38; Computational Geometry. 10(1), 47–65.
  mla: Bern, Marshall, et al. “Edge Insertion for Optimal Triangulations.” <i>Discrete
    &#38; Computational Geometry</i>, vol. 10, no. 1, Springer, 1993, pp. 47–65, doi:<a
    href="https://doi.org/10.1007/BF02573962">10.1007/BF02573962</a>.
  short: M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, T. Tan, Discrete &#38;
    Computational Geometry 10 (1993) 47–65.
date_created: 2018-12-11T12:06:36Z
date_published: 1993-12-01T00:00:00Z
date_updated: 2022-03-28T14:10:59Z
day: '01'
doi: 10.1007/BF02573962
extern: '1'
intvolume: '        10'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02573962
month: '12'
oa_version: None
page: 47 - 65
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2082'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Edge insertion for optimal triangulations
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 10
year: '1993'
...
---
_id: '4045'
abstract:
- lang: eng
  text: We apply Megiddo's parametric searching technique to several geometric optimization
    problems and derive significantly improved solutions for them. We obtain, for
    any fixed ε&gt;0, an O(n1+ε) algorithm for computing the diameter of a point set
    in 3-space, an O(8/5+ε) algorithm for computing the width of such a set, and on
    O(n8/5+ε) algorithm for computing the closest pair in a set of n lines in space.
    All these algorithms are deterministic.
acknowledgement: '*Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352.
  Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas
  Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational
  Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284,
  by NSF Grant CCR-89-01484, and by grants from the Fund for Basic Research administered
  by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation
  for Scientific Research and Development.'
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
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: Chazelle B, Edelsbrunner H, Guibas L, Sharir M. Diameter, width, closest line
    pair, and parametric searching. <i>Discrete &#38; Computational Geometry</i>.
    1993;10(1):183-196. doi:<a href="https://doi.org/10.1007/BF02573973">10.1007/BF02573973</a>
  apa: Chazelle, B., Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1993). Diameter,
    width, closest line pair, and parametric searching. <i>Discrete &#38; Computational
    Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02573973">https://doi.org/10.1007/BF02573973</a>
  chicago: Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir.
    “Diameter, Width, Closest Line Pair, and Parametric Searching.” <i>Discrete &#38;
    Computational Geometry</i>. Springer, 1993. <a href="https://doi.org/10.1007/BF02573973">https://doi.org/10.1007/BF02573973</a>.
  ieee: B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “Diameter, width,
    closest line pair, and parametric searching,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 10, no. 1. Springer, pp. 183–196, 1993.
  ista: Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1993. Diameter, width, closest
    line pair, and parametric searching. Discrete &#38; Computational Geometry. 10(1),
    183–196.
  mla: Chazelle, Bernard, et al. “Diameter, Width, Closest Line Pair, and Parametric
    Searching.” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1, Springer,
    1993, pp. 183–96, doi:<a href="https://doi.org/10.1007/BF02573973">10.1007/BF02573973</a>.
  short: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational
    Geometry 10 (1993) 183–196.
date_created: 2018-12-11T12:06:37Z
date_published: 1993-12-01T00:00:00Z
date_updated: 2022-03-28T14:50:42Z
day: '01'
doi: 10.1007/BF02573973
extern: '1'
intvolume: '        10'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02573973
month: '12'
oa_version: None
page: 183 - 196
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2083'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Diameter, width, closest line pair, and parametric searching
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 10
year: '1993'
...
---
_id: '4061'
abstract:
- lang: eng
  text: We present an algorithm to compute a Euclidean minimum spanning tree of a
    given set S of N points in Ed in time O(Fd (N,N) logd N), where Fd (n,m) is the
    time required to compute a bichromatic closest pair among n red and m green points
    in Ed . If Fd (N,N)=Ω(N1+ε), for some fixed e{open}&gt;0, then the running time
    improves to O(Fd (N,N)). Furthermore, we describe a randomized algorithm to compute
    a bichromatic closest pair in expected time O((nm log n log m)2/3+m log2 n+n log2
    m) in E3, which yields an O(N4/3 log4/3 N) expected time, algorithm for computing
    a Euclidean minimum spanning tree of N points in E3. In d≥4 dimensions we obtain
    expected time O((nm)1-1/([d/2]+1)+ε+m log n+n log m) for the bichromatic closest
    pair problem and O(N2-2/([d/2]+1)ε) for the Euclidean minimum spanning tree problem,
    for any positive e{open}.
acknowledgement: The first, second, and fourth authors acknowledge support from the
  Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National
  Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The
  second author's work was supported by the National Science Foundation under Grant
  CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft
  under Grant A1 253/1-3, Schwerpunktprogramm "Datenstrukturen und effiziente Algorithmen."
  The last two authors' work was also partially supported by the ESPRIT II Basic Research
  Action of the EC under Contract No. 3075 (project ALCOM).
article_processing_charge: No
article_type: original
author:
- first_name: Pankaj
  full_name: Agarwal, Pankaj
  last_name: Agarwal
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Otfried
  full_name: Schwarzkopf, Otfried
  last_name: Schwarzkopf
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. Euclidean minimum spanning
    trees and bichromatic closest pairs. <i>Discrete &#38; Computational Geometry</i>.
    1991;6(1):407-422. doi:<a href="https://doi.org/10.1007/BF02574698">10.1007/BF02574698</a>
  apa: Agarwal, P., Edelsbrunner, H., Schwarzkopf, O., &#38; Welzl, E. (1991). Euclidean
    minimum spanning trees and bichromatic closest pairs. <i>Discrete &#38; Computational
    Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02574698">https://doi.org/10.1007/BF02574698</a>
  chicago: Agarwal, Pankaj, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl.
    “Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” <i>Discrete
    &#38; Computational Geometry</i>. Springer, 1991. <a href="https://doi.org/10.1007/BF02574698">https://doi.org/10.1007/BF02574698</a>.
  ieee: P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, “Euclidean minimum
    spanning trees and bichromatic closest pairs,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 6, no. 1. Springer, pp. 407–422, 1991.
  ista: Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. 1991. Euclidean minimum
    spanning trees and bichromatic closest pairs. Discrete &#38; Computational Geometry.
    6(1), 407–422.
  mla: Agarwal, Pankaj, et al. “Euclidean Minimum Spanning Trees and Bichromatic Closest
    Pairs.” <i>Discrete &#38; Computational Geometry</i>, vol. 6, no. 1, Springer,
    1991, pp. 407–22, doi:<a href="https://doi.org/10.1007/BF02574698">10.1007/BF02574698</a>.
  short: P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, Discrete &#38; Computational
    Geometry 6 (1991) 407–422.
date_created: 2018-12-11T12:06:42Z
date_published: 1991-12-01T00:00:00Z
date_updated: 2022-02-24T15:06:41Z
day: '01'
doi: 10.1007/BF02574698
extern: '1'
intvolume: '         6'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://link.springer.com/article/10.1007/BF02574698
month: '12'
oa: 1
oa_version: Published Version
page: 407 - 422
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2062'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Euclidean minimum spanning trees and bichromatic closest pairs
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 6
year: '1991'
...
---
_id: '4062'
abstract:
- lang: eng
  text: We prove that for any set S of n points in the plane and n3-α triangles spanned
    by the points in S there exists a point (not necessarily in S) contained in at
    least n3-3α/(c log5 n) of the triangles. This implies that any set of n points
    in three-dimensional space defines at most {Mathematical expression} halving planes.
acknowledgement: "Work on this paper by Boris Aronov and Rephael Wenger has been supported
  by DIMACS under NSF Grant STC-88-09648. Work on this paper by Bernard Chazelle has
  been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrunner has been
  supported by NSF Grant CCR-87-14565. Micha Sharir has been supported by ONR Grant
  N00014-87-K-0129, by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli
  Binational Science Foundation, the Israeli National Council for Research and Development,
  and the Fund for Basic Research administered by the Israeli\r\nAcademy of Sciences"
article_processing_charge: No
article_type: original
author:
- first_name: Boris
  full_name: Aronov, Boris
  last_name: Aronov
- 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
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
- first_name: Rephael
  full_name: Wenger, Rephael
  last_name: Wenger
citation:
  ama: Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. Points
    and triangles in the plane and halving planes in space. <i>Discrete &#38; Computational
    Geometry</i>. 1991;6(1):435-442. doi:<a href="https://doi.org/10.1007/BF02574700">10.1007/BF02574700</a>
  apa: Aronov, B., Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Wenger,
    R. (1991). Points and triangles in the plane and halving planes in space. <i>Discrete
    &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02574700">https://doi.org/10.1007/BF02574700</a>
  chicago: Aronov, Boris, Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas,
    Micha Sharir, and Rephael Wenger. “Points and Triangles in the Plane and Halving
    Planes in Space.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1991.
    <a href="https://doi.org/10.1007/BF02574700">https://doi.org/10.1007/BF02574700</a>.
  ieee: B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and R. Wenger,
    “Points and triangles in the plane and halving planes in space,” <i>Discrete &#38;
    Computational Geometry</i>, vol. 6, no. 1. Springer, pp. 435–442, 1991.
  ista: Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. 1991.
    Points and triangles in the plane and halving planes in space. Discrete &#38;
    Computational Geometry. 6(1), 435–442.
  mla: Aronov, Boris, et al. “Points and Triangles in the Plane and Halving Planes
    in Space.” <i>Discrete &#38; Computational Geometry</i>, vol. 6, no. 1, Springer,
    1991, pp. 435–42, doi:<a href="https://doi.org/10.1007/BF02574700">10.1007/BF02574700</a>.
  short: B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, R. Wenger,
    Discrete &#38; Computational Geometry 6 (1991) 435–442.
date_created: 2018-12-11T12:06:43Z
date_published: 1991-12-01T00:00:00Z
date_updated: 2022-02-24T15:39:25Z
day: '01'
doi: 10.1007/BF02574700
extern: '1'
intvolume: '         6'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://link.springer.com/article/10.1007/BF02574700
month: '12'
oa: 1
oa_version: Published Version
page: 435 - 442
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2063'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Points and triangles in the plane and halving planes in space
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 6
year: '1991'
...
---
_id: '4066'
abstract:
- lang: eng
  text: 'We consider several problems involving points and planes in three dimensions.
    Our main results are: (i) The maximum number of faces boundingm distinct cells
    in an arrangement ofn planes isO(m 2/3 n logn +n 2); we can calculatem such cells
    specified by a point in each, in worst-case timeO(m 2/3 n log3 n+n 2 logn). (ii)
    The maximum number of incidences betweenn planes andm vertices of their arrangement
    isO(m 2/3 n logn+n 2), but this number is onlyO(m 3/5– n 4/5+2 +m+n logm), for
    any&gt;0, for any collection of points no three of which are collinear. (iii)
    For an arbitrary collection ofm points, we can calculate the number of incidences
    between them andn planes by a randomized algorithm whose expected time complexity
    isO((m 3/4– n 3/4+3 +m) log2 n+n logn logm) for any&gt;0. (iv) Givenm points andn
    planes, we can find the plane lying immediately below each point in randomized
    expected timeO([m 3/4– n 3/4+3 +m] log2 n+n logn logm) for any&gt;0. (v) The maximum
    number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an
    arrangement ofn hyperplanes ind dimensions,d&gt;3, isO(m 2/3 n d/3 logn+n d–1).
    This is also an upper bound for the number of incidences betweenn hyperplanes
    ind dimensions andm vertices of their arrangement. The combinatorial bounds in
    (i) and (v) and the general bound in (ii) are almost tight.'
acknowledgement: "Supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by
  NSF Grant CCR-8714565. Work on this paper by the first author has been supported
  by Amoco Fnd. Fac. Dev. Comput. Sci. I-6-44862 and by NSF Grant CCR-87t4565. Work
  by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129,
  by National Science Foundation Grant DCR-82-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. An abstract of this\r\npaper
  has appeared in the Proceedings of the 13th International Mathematical Programming
  Symposium, Tokyo, 1988, p. 147"
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: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: Edelsbrunner H, Guibas L, Sharir M. The complexity of many cells in arrangements
    of planes and related problems. <i>Discrete &#38; Computational Geometry</i>.
    1990;5(1):197-216. doi:<a href="https://doi.org/10.1007/BF02187785">10.1007/BF02187785</a>
  apa: Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1990). The complexity of many
    cells in arrangements of planes and related problems. <i>Discrete &#38; Computational
    Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187785">https://doi.org/10.1007/BF02187785</a>
  chicago: Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity
    of Many Cells in Arrangements of Planes and Related Problems.” <i>Discrete &#38;
    Computational Geometry</i>. Springer, 1990. <a href="https://doi.org/10.1007/BF02187785">https://doi.org/10.1007/BF02187785</a>.
  ieee: H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity of many cells in
    arrangements of planes and related problems,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 5, no. 1. Springer, pp. 197–216, 1990.
  ista: Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity of many cells in
    arrangements of planes and related problems. Discrete &#38; Computational Geometry.
    5(1), 197–216.
  mla: Edelsbrunner, Herbert, et al. “The Complexity of Many Cells in Arrangements
    of Planes and Related Problems.” <i>Discrete &#38; Computational Geometry</i>,
    vol. 5, no. 1, Springer, 1990, pp. 197–216, doi:<a href="https://doi.org/10.1007/BF02187785">10.1007/BF02187785</a>.
  short: H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry
    5 (1990) 197–216.
date_created: 2018-12-11T12:06:44Z
date_published: 1990-03-01T00:00:00Z
date_updated: 2022-02-22T11:02:41Z
day: '01'
doi: 10.1007/BF02187785
extern: '1'
intvolume: '         5'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187785
month: '03'
oa_version: None
page: 197 - 216
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2054'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The complexity of many cells in arrangements of planes and related problems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...
---
_id: '4068'
abstract:
- lang: eng
  text: "LetS be a collection ofn convex, closed, and pairwise nonintersecting sets
    in the Euclidean plane labeled from 1 ton. A pair of permutations\r\n(i1i2in−1in)(inin−1i2i1)
    \r\nis called ageometric permutation of S if there is a line that intersects all
    sets ofS in this order. We prove thatS can realize at most 2n–2 geometric permutations.
    This upper bound is tight."
acknowledgement: Research of the first author was supported by Amoco Foundation for
  Faculty Development in Computer Science Grant No. 1-6-44862. Work on this paper
  by the second author was supported by Office of Naval Research Grant No. N00014-82-K-0381,
  National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital
  Equipment Corporation and the IBM Corporation.
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: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: Edelsbrunner H, Sharir M. The maximum number of ways to stabn convex nonintersecting
    sets in the plane is 2n−2. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):35-42.
    doi:<a href="https://doi.org/10.1007/BF02187778">10.1007/BF02187778</a>
  apa: Edelsbrunner, H., &#38; Sharir, M. (1990). The maximum number of ways to stabn
    convex nonintersecting sets in the plane is 2n−2. <i>Discrete &#38; Computational
    Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187778">https://doi.org/10.1007/BF02187778</a>
  chicago: Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to
    Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” <i>Discrete &#38; Computational
    Geometry</i>. Springer, 1990. <a href="https://doi.org/10.1007/BF02187778">https://doi.org/10.1007/BF02187778</a>.
  ieee: H. Edelsbrunner and M. Sharir, “The maximum number of ways to stabn convex
    nonintersecting sets in the plane is 2n−2,” <i>Discrete &#38; Computational Geometry</i>,
    vol. 5, no. 1. Springer, pp. 35–42, 1990.
  ista: Edelsbrunner H, Sharir M. 1990. The maximum number of ways to stabn convex
    nonintersecting sets in the plane is 2n−2. Discrete &#38; Computational Geometry.
    5(1), 35–42.
  mla: Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn
    Convex Nonintersecting Sets in the Plane Is 2n−2.” <i>Discrete &#38; Computational
    Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 35–42, doi:<a href="https://doi.org/10.1007/BF02187778">10.1007/BF02187778</a>.
  short: H. Edelsbrunner, M. Sharir, Discrete &#38; Computational Geometry 5 (1990)
    35–42.
date_created: 2018-12-11T12:06:45Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-22T14:50:34Z
day: '01'
doi: 10.1007/BF02187778
extern: '1'
intvolume: '         5'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187778
month: '01'
oa_version: None
page: 35 - 42
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2057'
quality_controlled: '1'
status: public
title: The maximum number of ways to stabn convex nonintersecting sets in the plane
  is 2n−2
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...
---
_id: '4072'
abstract:
- lang: eng
  text: We show that the total number of edges ofm faces of an arrangement ofn lines
    in the plane isO(m 2/3– n 2/3+2 +n) for any&gt;0. The proof takes an algorithmic
    approach, that is, we describe an algorithm for the calculation of thesem faces
    and derive the upper bound from the analysis of the algorithm. The algorithm uses
    randomization and its expected time complexity isO(m 2/3– n 2/3+2 logn+n logn
    logm). If instead of lines we have an arrangement ofn line segments, then the
    maximum number of edges ofm faces isO(m 2/3– n 2/3+2 +n (n) logm) for any&gt;0,
    where(n) is the functional inverse of Ackermann's function. We give a (randomized)
    algorithm that produces these faces and takes expected timeO(m 2/3– n 2/3+2 log+n(n)
    log2 n logm).
acknowledgement: The first author is pleased to acknowledge partial support by the
  Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation
  under Grant CCR-8714565. Work on this paper by the third author has been supported
  by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation
  Grant 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. A preliminary version of this paper has appeared in
  theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55.
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: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: Edelsbrunner H, Guibas L, Sharir M. The complexity and construction of many
    faces in arrangements of lines and of segments. <i>Discrete &#38; Computational
    Geometry</i>. 1990;5(1):161-196. doi:<a href="https://doi.org/10.1007/BF02187784">10.1007/BF02187784</a>
  apa: Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1990). The complexity and construction
    of many faces in arrangements of lines and of segments. <i>Discrete &#38; Computational
    Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187784">https://doi.org/10.1007/BF02187784</a>
  chicago: Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity
    and Construction of Many Faces in Arrangements of Lines and of Segments.” <i>Discrete
    &#38; Computational Geometry</i>. Springer, 1990. <a href="https://doi.org/10.1007/BF02187784">https://doi.org/10.1007/BF02187784</a>.
  ieee: H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity and construction
    of many faces in arrangements of lines and of segments,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 5, no. 1. Springer, pp. 161–196, 1990.
  ista: Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity and construction
    of many faces in arrangements of lines and of segments. Discrete &#38; Computational
    Geometry. 5(1), 161–196.
  mla: Edelsbrunner, Herbert, et al. “The Complexity and Construction of Many Faces
    in Arrangements of Lines and of Segments.” <i>Discrete &#38; Computational Geometry</i>,
    vol. 5, no. 1, Springer, 1990, pp. 161–96, doi:<a href="https://doi.org/10.1007/BF02187784">10.1007/BF02187784</a>.
  short: H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry
    5 (1990) 161–196.
date_created: 2018-12-11T12:06:46Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-22T09:27:30Z
day: '01'
doi: 10.1007/BF02187784
extern: '1'
intvolume: '         5'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187784
month: '01'
oa_version: None
page: 161 - 196
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2053'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The complexity and construction of many faces in arrangements of lines and
  of segments
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...
---
_id: '4074'
abstract:
- lang: eng
  text: We present upper and lower bounds for extremal problems defined for arrangements
    of lines, circles, spheres, and alike. For example, we prove that the maximum
    number of edges boundingm cells in an arrangement ofn lines is Θ(m 2/3 n 2/3 +n),
    and that it isO(m 2/3 n 2/3 β(n) +n) forn unit-circles, whereβ(n) (and laterβ(m,
    n)) is a function that depends on the inverse of Ackermann's function and grows
    extremely slowly. If we replace unit-circles by circles of arbitrary radii the
    upper bound goes up toO(m 3/5 n 4/5 β(n) +n). The same bounds (without theβ(n)-terms)
    hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees
    in arrangements of lines and of unit-circles our bounds match previous results,
    but our proofs are considerably simpler than the previous ones. The maximum sum
    of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m
    4/7 n 9/7 β(m, n) +n 2), in general, andO(m 3/4 n 3/4 β(m, n) +n) if no three
    spheres intersect in a common circle. The latter bound implies that the maximum
    number of unit-distances amongm points in three dimensions isO(m 3/2 β(m)) which
    improves the best previous upper bound on this problem. Applications of our results
    to other distance problems are also given.
acknowledgement: The research of the second author was supported by the National Science
  Foundation under Grant CCR-8714565. Work by the fourth author has been supported
  by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation
  Grant No. 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. A preliminary version of this paper has appeared
  in theProceedings of the 29th IEEE Symposium on Foundations of Computer Science,
  1988.
article_processing_charge: No
article_type: original
author:
- first_name: Kenneth
  full_name: Clarkson, Kenneth
  last_name: Clarkson
- 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: Micha
  full_name: Sharir, Micha
  last_name: Sharir
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. Combinatorial complexity
    bounds for arrangements of curves and spheres. <i>Discrete &#38; Computational
    Geometry</i>. 1990;5(1):99-160. doi:<a href="https://doi.org/10.1007/BF02187783">10.1007/BF02187783</a>
  apa: Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Welzl, E. (1990).
    Combinatorial complexity bounds for arrangements of curves and spheres. <i>Discrete
    &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187783">https://doi.org/10.1007/BF02187783</a>
  chicago: Clarkson, Kenneth, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir,
    and Emo Welzl. “Combinatorial Complexity Bounds for Arrangements of Curves and
    Spheres.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href="https://doi.org/10.1007/BF02187783">https://doi.org/10.1007/BF02187783</a>.
  ieee: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, “Combinatorial
    complexity bounds for arrangements of curves and spheres,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 5, no. 1. Springer, pp. 99–160, 1990.
  ista: Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. 1990. Combinatorial
    complexity bounds for arrangements of curves and spheres. Discrete &#38; Computational
    Geometry. 5(1), 99–160.
  mla: Clarkson, Kenneth, et al. “Combinatorial Complexity Bounds for Arrangements
    of Curves and Spheres.” <i>Discrete &#38; Computational Geometry</i>, vol. 5,
    no. 1, Springer, 1990, pp. 99–160, doi:<a href="https://doi.org/10.1007/BF02187783">10.1007/BF02187783</a>.
  short: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Discrete &#38;
    Computational Geometry 5 (1990) 99–160.
date_created: 2018-12-11T12:06:47Z
date_published: 1990-03-01T00:00:00Z
date_updated: 2022-02-17T15:41:04Z
day: '01'
doi: 10.1007/BF02187783
extern: '1'
intvolume: '         5'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187783
month: '03'
oa_version: None
page: 99 - 160
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2048'
quality_controlled: '1'
status: public
title: Combinatorial complexity bounds for arrangements of curves and spheres
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...
---
_id: '4081'
abstract:
- lang: eng
  text: This paper studies applications of envelopes of piecewise linear functions
    to problems in computational geometry. Among these applications we find problems
    involving hidden line/surface elimination, motion planning, transversals of polytopes,
    and a new type of Voronoi diagram for clusters of points. All results are either
    combinatorial or computational in nature. They are based on the combinatorial
    analysis in two companion papers [PS] and [E2] and a divide-and-conquer algorithm
    for computing envelopes described in this paper.
acknowledgement: Work on this paper by the first author has been supported by Amoco
  Fnd. Fac. Dev. Comput. Sci. 1-6-44862. Work by the third author has been supported
  by the Office of Naval Research Grant N00014-82-K-0381, National Science Foundation
  Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and
  the IBM Corporation, and by a research grant from NCRD, the Israeli National Council
  for Research and Development.
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: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: 'Edelsbrunner H, Guibas L, Sharir M. The upper envelope of piecewise linear
    functions: Algorithms and applications. <i>Discrete &#38; Computational Geometry</i>.
    1989;4(1):311-336. doi:<a href="https://doi.org/10.1007/BF02187733">10.1007/BF02187733</a>'
  apa: 'Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1989). The upper envelope
    of piecewise linear functions: Algorithms and applications. <i>Discrete &#38;
    Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187733">https://doi.org/10.1007/BF02187733</a>'
  chicago: 'Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Upper Envelope
    of Piecewise Linear Functions: Algorithms and Applications.” <i>Discrete &#38;
    Computational Geometry</i>. Springer, 1989. <a href="https://doi.org/10.1007/BF02187733">https://doi.org/10.1007/BF02187733</a>.'
  ieee: 'H. Edelsbrunner, L. Guibas, and M. Sharir, “The upper envelope of piecewise
    linear functions: Algorithms and applications,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 4, no. 1. Springer, pp. 311–336, 1989.'
  ista: 'Edelsbrunner H, Guibas L, Sharir M. 1989. The upper envelope of piecewise
    linear functions: Algorithms and applications. Discrete &#38; Computational Geometry.
    4(1), 311–336.'
  mla: 'Edelsbrunner, Herbert, et al. “The Upper Envelope of Piecewise Linear Functions:
    Algorithms and Applications.” <i>Discrete &#38; Computational Geometry</i>, vol.
    4, no. 1, Springer, 1989, pp. 311–36, doi:<a href="https://doi.org/10.1007/BF02187733">10.1007/BF02187733</a>.'
  short: H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry
    4 (1989) 311–336.
date_created: 2018-12-11T12:06:50Z
date_published: 1989-12-01T00:00:00Z
date_updated: 2022-02-10T15:53:48Z
day: '01'
doi: 10.1007/BF02187733
extern: '1'
intvolume: '         4'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://link.springer.com/article/10.1007/BF02187733
month: '12'
oa: 1
oa_version: Published Version
page: 311 - 336
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2038'
quality_controlled: '1'
status: public
title: 'The upper envelope of piecewise linear functions: Algorithms and applications'
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1989'
...
---
_id: '4086'
abstract:
- lang: eng
  text: This note proves that the maximum number of faces (of any dimension) of the
    upper envelope of a set ofn possibly intersectingd-simplices ind+1 dimensions
    is (n d (n)). This is an extension of a result of Pach and Sharir [PS] who prove
    the same bound for the number ofd-dimensional faces of the upper envelope.
acknowledgement: "This work was supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862
  and by the National Science Foundation under Grant CCR-8714565. Research on the
  presented result was partially carried out while the author worked for the IBM T.
  J. Watson Research Center at Yorktown Height, New York, USA. \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
citation:
  ama: 'Edelsbrunner H. The upper envelope of piecewise linear functions: Tight bounds
    on the number of faces . <i>Discrete &#38; Computational Geometry</i>. 1989;4(4):337-343.
    doi:<a href="https://doi.org/10.1007/BF02187734">10.1007/BF02187734</a>'
  apa: 'Edelsbrunner, H. (1989). The upper envelope of piecewise linear functions:
    Tight bounds on the number of faces . <i>Discrete &#38; Computational Geometry</i>.
    Springer. <a href="https://doi.org/10.1007/BF02187734">https://doi.org/10.1007/BF02187734</a>'
  chicago: 'Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions:
    Tight Bounds on the Number of Faces .” <i>Discrete &#38; Computational Geometry</i>.
    Springer, 1989. <a href="https://doi.org/10.1007/BF02187734">https://doi.org/10.1007/BF02187734</a>.'
  ieee: 'H. Edelsbrunner, “The upper envelope of piecewise linear functions: Tight
    bounds on the number of faces ,” <i>Discrete &#38; Computational Geometry</i>,
    vol. 4, no. 4. Springer, pp. 337–343, 1989.'
  ista: 'Edelsbrunner H. 1989. The upper envelope of piecewise linear functions: Tight
    bounds on the number of faces . Discrete &#38; Computational Geometry. 4(4), 337–343.'
  mla: 'Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions:
    Tight Bounds on the Number of Faces .” <i>Discrete &#38; Computational Geometry</i>,
    vol. 4, no. 4, Springer, 1989, pp. 337–43, doi:<a href="https://doi.org/10.1007/BF02187734">10.1007/BF02187734</a>.'
  short: H. Edelsbrunner, Discrete &#38; Computational Geometry 4 (1989) 337–343.
date_created: 2018-12-11T12:06:51Z
date_published: 1989-11-01T00:00:00Z
date_updated: 2022-02-10T11:08:12Z
day: '01'
doi: 10.1007/BF02187734
extern: '1'
intvolume: '         4'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://link.springer.com/article/10.1007/BF02187734
month: '11'
oa: 1
oa_version: Published Version
page: 337 - 343
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2034'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The upper envelope of piecewise linear functions: Tight bounds on the number
  of faces '
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1989'
...