---
_id: '5920'
abstract:
- lang: eng
  text: We study chains of lattice ideals that are invariant under a symmetric group
    action. In our setting, the ambient rings for these ideals are polynomial rings
    which are increasing in (Krull) dimension. Thus, these chains will fail to stabilize
    in the traditional commutative algebra sense. However, we prove a theorem which
    says that “up to the action of the group”, these chains locally stabilize. We
    also give an algorithm, which we have implemented in software, for explicitly
    constructing these stabilization generators for a family of Laurent toric ideals
    involved in applications to algebraic statistics. We close with several open problems
    and conjectures arising from our theoretical and computational investigations.
article_processing_charge: No
article_type: original
author:
- first_name: Christopher J.
  full_name: Hillar, Christopher J.
  last_name: Hillar
- first_name: Abraham
  full_name: Martin del Campo Sanchez, Abraham
  id: 4CF47F6A-F248-11E8-B48F-1D18A9856A87
  last_name: Martin del Campo Sanchez
citation:
  ama: Hillar CJ, Martin del Campo Sanchez A. Finiteness theorems and algorithms for
    permutation invariant chains of Laurent lattice ideals. <i>Journal of Symbolic
    Computation</i>. 2013;50:314-334. doi:<a href="https://doi.org/10.1016/j.jsc.2012.06.006">10.1016/j.jsc.2012.06.006</a>
  apa: Hillar, C. J., &#38; Martin del Campo Sanchez, A. (2013). Finiteness theorems
    and algorithms for permutation invariant chains of Laurent lattice ideals. <i>Journal
    of Symbolic Computation</i>. Elsevier. <a href="https://doi.org/10.1016/j.jsc.2012.06.006">https://doi.org/10.1016/j.jsc.2012.06.006</a>
  chicago: Hillar, Christopher J., and Abraham Martin del Campo Sanchez. “Finiteness
    Theorems and Algorithms for Permutation Invariant Chains of Laurent Lattice Ideals.”
    <i>Journal of Symbolic Computation</i>. Elsevier, 2013. <a href="https://doi.org/10.1016/j.jsc.2012.06.006">https://doi.org/10.1016/j.jsc.2012.06.006</a>.
  ieee: C. J. Hillar and A. Martin del Campo Sanchez, “Finiteness theorems and algorithms
    for permutation invariant chains of Laurent lattice ideals,” <i>Journal of Symbolic
    Computation</i>, vol. 50. Elsevier, pp. 314–334, 2013.
  ista: Hillar CJ, Martin del Campo Sanchez A. 2013. Finiteness theorems and algorithms
    for permutation invariant chains of Laurent lattice ideals. Journal of Symbolic
    Computation. 50, 314–334.
  mla: Hillar, Christopher J., and Abraham Martin del Campo Sanchez. “Finiteness Theorems
    and Algorithms for Permutation Invariant Chains of Laurent Lattice Ideals.” <i>Journal
    of Symbolic Computation</i>, vol. 50, Elsevier, 2013, pp. 314–34, doi:<a href="https://doi.org/10.1016/j.jsc.2012.06.006">10.1016/j.jsc.2012.06.006</a>.
  short: C.J. Hillar, A. Martin del Campo Sanchez, Journal of Symbolic Computation
    50 (2013) 314–334.
date_created: 2019-02-05T08:48:24Z
date_published: 2013-03-01T00:00:00Z
date_updated: 2021-01-12T08:05:15Z
day: '01'
doi: 10.1016/j.jsc.2012.06.006
extern: '1'
intvolume: '        50'
language:
- iso: eng
month: '03'
oa_version: None
page: 314-334
publication: Journal of Symbolic Computation
publication_identifier:
  issn:
  - 0747-7171
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
  link:
  - relation: erratum
    url: https://doi.org/10.1016/j.jsc.2015.09.002
status: public
title: Finiteness theorems and algorithms for permutation invariant chains of Laurent
  lattice ideals
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 50
year: '2013'
...
---
_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'
...