---
_id: '4060'
abstract:
- lang: eng
  text: This paper offers combinatorial results on extremum problems concerning the
    number of tetrahedra in a tetrahedrization of n points in general position in
    three dimensions, i.e. such that no four points are co-planar, It also presents
    an algorithm that in O(n log n) time constructs a tetrahedrization of a set of
    n points consisting of at most 3n-11 tetrahedra.
acknowledgement: Research of the first author is supported by Amoco Fnd. Fac. Dec.
  Comput. Sci. 1-6-44862, the second author is supported by NSF Grant ECS 84-10902,
  and research of the third author is supported in part by ONR Grant N00014-85K0570
  and by NSF Grant DMS 8504322.
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: Franco
  full_name: Preparata, Franco
  last_name: Preparata
- first_name: Douglas
  full_name: West, Douglas
  last_name: West
citation:
  ama: Edelsbrunner H, Preparata F, West D. Tetrahedrizing point sets in three dimensions.
    <i>Journal of Symbolic Computation</i>. 1990;10(3-4):335-347. doi:<a href="https://doi.org/10.1016/S0747-7171(08)80068-5">10.1016/S0747-7171(08)80068-5</a>
  apa: Edelsbrunner, H., Preparata, F., &#38; West, D. (1990). Tetrahedrizing point
    sets in three dimensions. <i>Journal of Symbolic Computation</i>. Elsevier. <a
    href="https://doi.org/10.1016/S0747-7171(08)80068-5">https://doi.org/10.1016/S0747-7171(08)80068-5</a>
  chicago: Edelsbrunner, Herbert, Franco Preparata, and Douglas West. “Tetrahedrizing
    Point Sets in Three Dimensions.” <i>Journal of Symbolic Computation</i>. Elsevier,
    1990. <a href="https://doi.org/10.1016/S0747-7171(08)80068-5">https://doi.org/10.1016/S0747-7171(08)80068-5</a>.
  ieee: H. Edelsbrunner, F. Preparata, and D. West, “Tetrahedrizing point sets in
    three dimensions,” <i>Journal of Symbolic Computation</i>, vol. 10, no. 3–4. Elsevier,
    pp. 335–347, 1990.
  ista: Edelsbrunner H, Preparata F, West D. 1990. Tetrahedrizing point sets in three
    dimensions. Journal of Symbolic Computation. 10(3–4), 335–347.
  mla: Edelsbrunner, Herbert, et al. “Tetrahedrizing Point Sets in Three Dimensions.”
    <i>Journal of Symbolic Computation</i>, vol. 10, no. 3–4, Elsevier, 1990, pp.
    335–47, doi:<a href="https://doi.org/10.1016/S0747-7171(08)80068-5">10.1016/S0747-7171(08)80068-5</a>.
  short: H. Edelsbrunner, F. Preparata, D. West, Journal of Symbolic Computation 10
    (1990) 335–347.
date_created: 2018-12-11T12:06:42Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-23T10:10:35Z
day: '01'
doi: 10.1016/S0747-7171(08)80068-5
extern: '1'
intvolume: '        10'
issue: 3-4
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/S0747717108800685?via%3Dihub
month: '01'
oa: 1
oa_version: Published Version
page: 335 - 347
publication: Journal of Symbolic Computation
publication_identifier:
  eissn:
  - 1095-855X
  issn:
  - 0747-7171
publication_status: published
publisher: Elsevier
publist_id: '2061'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tetrahedrizing point sets in three dimensions
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 10
year: '1990'
...
---
_id: '4106'
abstract:
- lang: eng
  text: Let B be a set of nb black points and W a set of nw, white points in the Euclidean
    plane. A line h is said to bisect B (or W) if, at most, half of the points of
    B (or W) lie on any one side of h. A line that bisects both B and W is called
    a ham-sandwich cut of B and W. We give an algorithm that computes a ham-sandwich
    cut of B and W in 0((nh+nw) log (min {nb, nw}+ 1)) time. The algorithm is considerably
    simpler than the previous most efficient one which takes 0((nb + nw) log (nb +
    nw)) time.
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: Roman
  full_name: Waupotitsch, Roman
  last_name: Waupotitsch
citation:
  ama: Edelsbrunner H, Waupotitsch R. Computing a ham-sandwich cut in two dimensions.
    <i>Journal of Symbolic Computation</i>. 1986;2(2):171-178. doi:<a href="https://doi.org/10.1016/S0747-7171(86)80020-7">10.1016/S0747-7171(86)80020-7</a>
  apa: Edelsbrunner, H., &#38; Waupotitsch, R. (1986). Computing a ham-sandwich cut
    in two dimensions. <i>Journal of Symbolic Computation</i>. Elsevier. <a href="https://doi.org/10.1016/S0747-7171(86)80020-7">https://doi.org/10.1016/S0747-7171(86)80020-7</a>
  chicago: Edelsbrunner, Herbert, and Roman Waupotitsch. “Computing a Ham-Sandwich
    Cut in Two Dimensions.” <i>Journal of Symbolic Computation</i>. Elsevier, 1986.
    <a href="https://doi.org/10.1016/S0747-7171(86)80020-7">https://doi.org/10.1016/S0747-7171(86)80020-7</a>.
  ieee: H. Edelsbrunner and R. Waupotitsch, “Computing a ham-sandwich cut in two dimensions,”
    <i>Journal of Symbolic Computation</i>, vol. 2, no. 2. Elsevier, pp. 171–178,
    1986.
  ista: Edelsbrunner H, Waupotitsch R. 1986. Computing a ham-sandwich cut in two dimensions.
    Journal of Symbolic Computation. 2(2), 171–178.
  mla: Edelsbrunner, Herbert, and Roman Waupotitsch. “Computing a Ham-Sandwich Cut
    in Two Dimensions.” <i>Journal of Symbolic Computation</i>, vol. 2, no. 2, Elsevier,
    1986, pp. 171–78, doi:<a href="https://doi.org/10.1016/S0747-7171(86)80020-7">10.1016/S0747-7171(86)80020-7</a>.
  short: H. Edelsbrunner, R. Waupotitsch, Journal of Symbolic Computation 2 (1986)
    171–178.
date_created: 2018-12-11T12:06:58Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T11:22:59Z
day: '01'
doi: 10.1016/S0747-7171(86)80020-7
extern: '1'
intvolume: '         2'
issue: '2'
language:
- iso: eng
month: '01'
oa_version: None
page: 171 - 178
publication: Journal of Symbolic Computation
publication_identifier:
  eissn:
  - 1095-855X
  issn:
  - 0747-7171
publication_status: published
publisher: Elsevier
publist_id: '2018'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing a ham-sandwich cut in two dimensions
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2
year: '1986'
...
---
_id: '4120'
abstract:
- lang: eng
  text: 'Let P be a set of n points in the Euclidean plane and let C be a convex figure.
    We study the problem of preprocessing P so that for any query point q, the points
    of P in C+q can be retrieved efficiently. If constant time sumces for deciding
    the inclusion of a point in C, we then demonstrate the existence of an optimal
    solution: the algorithm requires O(n) space and O(k + log n) time for a query
    with output size k. If C is a disk, the problem becomes the wellknown fixed-radius
    neighbour problem, to which we thus provide the first known optimal solution.'
acknowledgement: The first author was supported i~1 part by NSF grants MCS 83-03925
  and the Office of Naval Research and the Defense Advanced Research Projects Agency
  under contract N00014-g3-K-0146 and ARPA Order No. 4786.
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. Optimal solutions for a class of point retrieval
    problems. <i>Journal of Symbolic Computation</i>. 1985;1(1):47-56. doi:<a href="https://doi.org/10.1016/S0747-7171(85)80028-6">10.1016/S0747-7171(85)80028-6</a>
  apa: Chazelle, B., &#38; Edelsbrunner, H. (1985). Optimal solutions for a class
    of point retrieval problems. <i>Journal of Symbolic Computation</i>. Elsevier.
    <a href="https://doi.org/10.1016/S0747-7171(85)80028-6">https://doi.org/10.1016/S0747-7171(85)80028-6</a>
  chicago: Chazelle, Bernard, and Herbert Edelsbrunner. “Optimal Solutions for a Class
    of Point Retrieval Problems.” <i>Journal of Symbolic Computation</i>. Elsevier,
    1985. <a href="https://doi.org/10.1016/S0747-7171(85)80028-6">https://doi.org/10.1016/S0747-7171(85)80028-6</a>.
  ieee: B. Chazelle and H. Edelsbrunner, “Optimal solutions for a class of point retrieval
    problems,” <i>Journal of Symbolic Computation</i>, vol. 1, no. 1. Elsevier, pp.
    47–56, 1985.
  ista: Chazelle B, Edelsbrunner H. 1985. Optimal solutions for a class of point retrieval
    problems. Journal of Symbolic Computation. 1(1), 47–56.
  mla: Chazelle, Bernard, and Herbert Edelsbrunner. “Optimal Solutions for a Class
    of Point Retrieval Problems.” <i>Journal of Symbolic Computation</i>, vol. 1,
    no. 1, Elsevier, 1985, pp. 47–56, doi:<a href="https://doi.org/10.1016/S0747-7171(85)80028-6">10.1016/S0747-7171(85)80028-6</a>.
  short: B. Chazelle, H. Edelsbrunner, Journal of Symbolic Computation 1 (1985) 47–56.
date_created: 2018-12-11T12:07:03Z
date_published: 1985-03-01T00:00:00Z
date_updated: 2022-01-31T09:20:18Z
day: '01'
doi: 10.1016/S0747-7171(85)80028-6
extern: '1'
intvolume: '         1'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/S0747717185800286?via%3Dihub
month: '03'
oa: 1
oa_version: Published Version
page: 47 - 56
publication: Journal of Symbolic Computation
publication_identifier:
  eissn:
  - 1095-855X
  issn:
  - 0747-7171
publication_status: published
publisher: Elsevier
publist_id: '2004'
quality_controlled: '1'
status: public
title: Optimal solutions for a class of point retrieval problems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1985'
...