---
_id: '9317'
abstract:
- lang: eng
text: Given a locally finite X⊆Rd and a radius r≥0, the k-fold cover of X and r
consists of all points in Rd that have k or more points of X within distance r.
We consider two filtrations—one in scale obtained by fixing k and increasing r,
and the other in depth obtained by fixing r and decreasing k—and we compute the
persistence diagrams of both. While standard methods suffice for the filtration
in scale, we need novel geometric and topological concepts for the filtration
in depth. In particular, we introduce a rhomboid tiling in Rd+1 whose horizontal
integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module
of Delaunay mosaics that is isomorphic to the persistence module of the multi-covers.
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(Grant Agreement No. 78818 Alpha), and by the DFG Collaborative Research Center
TRR 109, ‘Discretization in Geometry and Dynamics’, through Grant No. I02979-N35
of the Austrian Science Fund (FWF)\r\nOpen Access funding provided by the Institute
of Science and Technology (IST Austria)."
article_processing_charge: Yes (via OA deal)
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: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
orcid: 0000-0002-8882-5116
citation:
ama: Edelsbrunner H, Osang GF. The multi-cover persistence of Euclidean balls. Discrete
and Computational Geometry. 2021;65:1296–1313. doi:10.1007/s00454-021-00281-9
apa: Edelsbrunner, H., & Osang, G. F. (2021). The multi-cover persistence of
Euclidean balls. Discrete and Computational Geometry. Springer Nature.
https://doi.org/10.1007/s00454-021-00281-9
chicago: Edelsbrunner, Herbert, and Georg F Osang. “The Multi-Cover Persistence
of Euclidean Balls.” Discrete and Computational Geometry. Springer Nature,
2021. https://doi.org/10.1007/s00454-021-00281-9.
ieee: H. Edelsbrunner and G. F. Osang, “The multi-cover persistence of Euclidean
balls,” Discrete and Computational Geometry, vol. 65. Springer Nature,
pp. 1296–1313, 2021.
ista: Edelsbrunner H, Osang GF. 2021. The multi-cover persistence of Euclidean balls.
Discrete and Computational Geometry. 65, 1296–1313.
mla: Edelsbrunner, Herbert, and Georg F. Osang. “The Multi-Cover Persistence of
Euclidean Balls.” Discrete and Computational Geometry, vol. 65, Springer
Nature, 2021, pp. 1296–1313, doi:10.1007/s00454-021-00281-9.
short: H. Edelsbrunner, G.F. Osang, Discrete and Computational Geometry 65 (2021)
1296–1313.
corr_author: '1'
date_created: 2021-04-11T22:01:15Z
date_published: 2021-03-31T00:00:00Z
date_updated: 2025-06-12T06:36:54Z
day: '31'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.1007/s00454-021-00281-9
ec_funded: 1
external_id:
isi:
- '000635460400001'
pmid:
- '34720303'
file:
- access_level: open_access
checksum: 59b4e1e827e494209bcb4aae22e1d347
content_type: application/pdf
creator: cchlebak
date_created: 2021-12-01T10:56:53Z
date_updated: 2021-12-01T10:56:53Z
file_id: '10394'
file_name: 2021_DisCompGeo_Edelsbrunner_Osang.pdf
file_size: 677704
relation: main_file
success: 1
file_date_updated: 2021-12-01T10:56:53Z
has_accepted_license: '1'
intvolume: ' 65'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: 1296–1313
pmid: 1
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '187'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: The multi-cover persistence of Euclidean balls
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 65
year: '2021'
...
---
_id: '5986'
abstract:
- lang: eng
text: "Given a triangulation of a point set in the plane, a flip deletes an edge
e whose removal leaves a convex quadrilateral, and replaces e by the opposite
diagonal of the quadrilateral. It is well known that any triangulation of a point
set can be reconfigured to any other triangulation by some sequence of flips.
We explore this question in the setting where each edge of a triangulation has
a label, and a flip transfers the label of the removed edge to the new edge. It
is not true that every labelled triangulation of a point set can be reconfigured
to every other labelled triangulation via a sequence of flips, but we characterize
when this is possible. There is an obvious necessary condition: for each label
l, if edge e has label l in the first triangulation and edge f has label l in
the second triangulation, then there must be some sequence of flips that moves
label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot
formulated the Orbit Conjecture, which states that this necessary condition is
also sufficient, i.e. that all labels can be simultaneously mapped to their destination
if and only if each label individually can be mapped to its destination. We prove
this conjecture. Furthermore, we give a polynomial-time algorithm (with \U0001D442(\U0001D45B8)
being a crude bound on the run-time) to find a sequence of flips to reconfigure
one labelled triangulation to another, if such a sequence exists, and we prove
an upper bound of \U0001D442(\U0001D45B7) on the length of the flip sequence.
Our proof uses the topological result that the sets of pairwise non-crossing edges
on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional
ball (this follows from a result of Orden and Santos; we give a different proof
based on a shelling argument). The dual cell complex of this simplicial ball,
called the flip complex, has the usual flip graph as its 1-skeleton. We use properties
of the 2-skeleton of the flip complex to prove the Orbit Conjecture."
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Anna
full_name: Lubiw, Anna
last_name: Lubiw
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping
edge-labelled triangulations. Discrete & Computational Geometry. 2019;61(4):880-898.
doi:10.1007/s00454-018-0035-8
apa: Lubiw, A., Masárová, Z., & Wagner, U. (2019). A proof of the orbit conjecture
for flipping edge-labelled triangulations. Discrete & Computational Geometry.
Springer Nature. https://doi.org/10.1007/s00454-018-0035-8
chicago: Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture
for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry.
Springer Nature, 2019. https://doi.org/10.1007/s00454-018-0035-8.
ieee: A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for
flipping edge-labelled triangulations,” Discrete & Computational Geometry,
vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.
ista: Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping
edge-labelled triangulations. Discrete & Computational Geometry. 61(4), 880–898.
mla: Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled
Triangulations.” Discrete & Computational Geometry, vol. 61, no. 4,
Springer Nature, 2019, pp. 880–98, doi:10.1007/s00454-018-0035-8.
short: A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61
(2019) 880–898.
corr_author: '1'
date_created: 2019-02-14T11:54:08Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2026-04-08T07:23:01Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1007/s00454-018-0035-8
external_id:
arxiv:
- '1710.02741'
isi:
- '000466130000009'
file:
- access_level: open_access
checksum: e1bff88f1d77001b53b78c485ce048d7
content_type: application/pdf
creator: dernst
date_created: 2019-02-14T11:57:22Z
date_updated: 2020-07-14T12:47:14Z
file_id: '5988'
file_name: 2018_DiscreteGeometry_Lubiw.pdf
file_size: 556276
relation: main_file
file_date_updated: 2020-07-14T12:47:14Z
has_accepted_license: '1'
intvolume: ' 61'
isi: 1
issue: '4'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 880-898
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '683'
relation: earlier_version
status: public
- id: '7944'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: A proof of the orbit conjecture for flipping edge-labelled triangulations
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 61
year: '2019'
...
---
_id: '1064'
abstract:
- lang: eng
text: 'In 1945, A.W. Goodman and R.E. Goodman proved the following conjecture by
P. Erdős: Given a family of (round) disks of radii r1, … , rn in the plane, it
is always possible to cover them by a disk of radius R= ∑ ri, provided they cannot
be separated into two subfamilies by a straight line disjoint from the disks.
In this note we show that essentially the same idea may work for different analogues
and generalizations of their result. In particular, we prove the following: Given
a family of positive homothetic copies of a fixed convex body K⊂ Rd with homothety
coefficients τ1, … , τn> 0 , it is always possible to cover them by a translate
of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane
disjoint from the homothets.'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Alexey
full_name: Balitskiy, Alexey
last_name: Balitskiy
- first_name: Mikhail
full_name: Grigorev, Mikhail
last_name: Grigorev
citation:
ama: Akopyan A, Balitskiy A, Grigorev M. On the circle covering theorem by A.W.
Goodman and R.E. Goodman. Discrete & Computational Geometry. 2018;59(4):1001-1009.
doi:10.1007/s00454-017-9883-x
apa: Akopyan, A., Balitskiy, A., & Grigorev, M. (2018). On the circle covering
theorem by A.W. Goodman and R.E. Goodman. Discrete & Computational Geometry.
Springer. https://doi.org/10.1007/s00454-017-9883-x
chicago: Akopyan, Arseniy, Alexey Balitskiy, and Mikhail Grigorev. “On the Circle
Covering Theorem by A.W. Goodman and R.E. Goodman.” Discrete & Computational
Geometry. Springer, 2018. https://doi.org/10.1007/s00454-017-9883-x.
ieee: A. Akopyan, A. Balitskiy, and M. Grigorev, “On the circle covering theorem
by A.W. Goodman and R.E. Goodman,” Discrete & Computational Geometry,
vol. 59, no. 4. Springer, pp. 1001–1009, 2018.
ista: Akopyan A, Balitskiy A, Grigorev M. 2018. On the circle covering theorem by
A.W. Goodman and R.E. Goodman. Discrete & Computational Geometry. 59(4), 1001–1009.
mla: Akopyan, Arseniy, et al. “On the Circle Covering Theorem by A.W. Goodman and
R.E. Goodman.” Discrete & Computational Geometry, vol. 59, no. 4, Springer,
2018, pp. 1001–09, doi:10.1007/s00454-017-9883-x.
short: A. Akopyan, A. Balitskiy, M. Grigorev, Discrete & Computational Geometry
59 (2018) 1001–1009.
corr_author: '1'
date_created: 2018-12-11T11:49:57Z
date_published: 2018-06-01T00:00:00Z
date_updated: 2026-05-20T10:19:33Z
day: '01'
ddc:
- '516'
- '000'
department:
- _id: HeEd
doi: 10.1007/s00454-017-9883-x
ec_funded: 1
external_id:
isi:
- '000432205500011'
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2019-01-18T09:27:36Z
date_updated: 2019-01-18T09:27:36Z
file_id: '5844'
file_name: 2018_DiscreteComp_Akopyan.pdf
file_size: 482518
relation: main_file
success: 1
file_date_updated: 2019-01-18T09:27:36Z
has_accepted_license: '1'
intvolume: ' 59'
isi: 1
issue: '4'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 1001-1009
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '6324'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the circle covering theorem by A.W. Goodman and R.E. Goodman
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 59
year: '2018'
...
---
OA_place: repository
OA_type: green
_id: '22198'
abstract:
- lang: eng
text: "Packings of equal disks in the plane are known to have density at most\r\nπ/\r\n√\r\n12,
although this density is never achieved in the square torus, which is what we\r\ncall
the plane modulo the square lattice. We find packings of disks in a square torus\r\nthat
we conjecture to be the most dense for certain numbers of packing disks, using\r\ncontinued
fractions to approximate 1/\r\n√\r\n3 and 2 −\r\n√\r\n3. We also define a constant
to\r\nmeasure the efficiency of a packing motived by a related constant due to
Markov for\r\ncontinued fractions. One idea is to use the unique factorization
property of Gaussian\r\nintegers to prove that there is an upper bound for the
Markov constant for grid-like\r\npackings. By way of contrast, we show that an
upper bound by Gruber [In many cases\r\noptimal configurations are almost regular
hexagonal, vol. 65, pp. 121–145, 1999;Geom\r\nDedicata 84(1–3):271–320, 2001]
for the error for the limiting density of a packing\r\nof equal disks in a planar
square, which is on the order of 1/\r\n√\r\nN, is the best possible,\r\nwhereas
for our examples for the square torus, the error for the limiting density is on\r\nthe
order of 1/N, where N is the number of packing disks."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Robert
full_name: Connelly, Robert
last_name: Connelly
- first_name: Matthew
full_name: Funkhouser, Matthew
last_name: Funkhouser
- first_name: Vivian Zieve
full_name: Kuperberg, Vivian Zieve
id: c3bac823-112d-11f0-a3f5-c264f852e697
last_name: Kuperberg
- first_name: Evan
full_name: Solomonides, Evan
last_name: Solomonides
citation:
ama: Connelly R, Funkhouser M, Kuperberg VZ, Solomonides E. Packings of equal disks
in a square torus. Discrete & Computational Geometry. 2017;58(3):614-642.
doi:10.1007/s00454-016-9843-x
apa: Connelly, R., Funkhouser, M., Kuperberg, V. Z., & Solomonides, E. (2017).
Packings of equal disks in a square torus. Discrete & Computational Geometry.
Springer Nature. https://doi.org/10.1007/s00454-016-9843-x
chicago: Connelly, Robert, Matthew Funkhouser, Vivian Zieve Kuperberg, and Evan
Solomonides. “Packings of Equal Disks in a Square Torus.” Discrete & Computational
Geometry. Springer Nature, 2017. https://doi.org/10.1007/s00454-016-9843-x.
ieee: R. Connelly, M. Funkhouser, V. Z. Kuperberg, and E. Solomonides, “Packings
of equal disks in a square torus,” Discrete & Computational Geometry,
vol. 58, no. 3. Springer Nature, pp. 614–642, 2017.
ista: Connelly R, Funkhouser M, Kuperberg VZ, Solomonides E. 2017. Packings of equal
disks in a square torus. Discrete & Computational Geometry. 58(3), 614–642.
mla: Connelly, Robert, et al. “Packings of Equal Disks in a Square Torus.” Discrete
& Computational Geometry, vol. 58, no. 3, Springer Nature, 2017, pp. 614–42,
doi:10.1007/s00454-016-9843-x.
short: R. Connelly, M. Funkhouser, V.Z. Kuperberg, E. Solomonides, Discrete &
Computational Geometry 58 (2017) 614–642.
date_created: 2026-06-29T12:58:50Z
date_published: 2017-01-09T00:00:00Z
date_updated: 2026-07-14T11:14:51Z
day: '09'
doi: 10.1007/s00454-016-9843-x
extern: '1'
external_id:
arxiv:
- '1512.08762'
intvolume: ' 58'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://doi.org/10.48550/arXiv.1512.08762
month: '01'
oa_version: Preprint
page: 614-642
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Packings of equal disks in a square torus
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 58
year: '2017'
...
---
_id: '2815'
abstract:
- lang: eng
text: The fact that a sum of isotropic Gaussian kernels can have more modes than
kernels is surprising. Extra (ghost) modes do not exist in ℝ1 and are generally
not well studied in higher dimensions. We study a configuration of n+1 Gaussian
kernels for which there are exactly n+2 modes. We show that all modes lie on a
finite set of lines, which we call axes, and study the restriction of the Gaussian
mixture to these axes in order to discover that there are an exponential number
of critical points in this configuration. Although the existence of ghost modes
remained unknown due to the difficulty of finding examples in ℝ2, we show that
the resilience of ghost modes grows like the square root of the dimension. In
addition, we exhibit finite configurations of isotropic Gaussian kernels with
superlinearly many modes.
acknowledgement: This research is partially supported by the National Science Foundation
(NSF) under Grant DBI-0820624, by the European Science Foundation under the Research
Networking Programme, and the Russian Government Project 11.G34.31.0053.
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: Brittany Terese
full_name: Fasy, Brittany Terese
id: F65D502E-E68D-11E9-9252-C644099818F6
last_name: Fasy
- first_name: Günter
full_name: Rote, Günter
last_name: Rote
citation:
ama: 'Edelsbrunner H, Fasy BT, Rote G. Add isotropic Gaussian kernels at own risk:
More and more resilient modes in higher dimensions. Discrete & Computational
Geometry. 2013;49(4):797-822. doi:10.1007/s00454-013-9517-x'
apa: 'Edelsbrunner, H., Fasy, B. T., & Rote, G. (2013). Add isotropic Gaussian
kernels at own risk: More and more resilient modes in higher dimensions. Discrete
& Computational Geometry. Springer. https://doi.org/10.1007/s00454-013-9517-x'
chicago: 'Edelsbrunner, Herbert, Brittany Terese Fasy, and Günter Rote. “Add Isotropic
Gaussian Kernels at Own Risk: More and More Resilient Modes in Higher Dimensions.”
Discrete & Computational Geometry. Springer, 2013. https://doi.org/10.1007/s00454-013-9517-x.'
ieee: 'H. Edelsbrunner, B. T. Fasy, and G. Rote, “Add isotropic Gaussian kernels
at own risk: More and more resilient modes in higher dimensions,” Discrete
& Computational Geometry, vol. 49, no. 4. Springer, pp. 797–822, 2013.'
ista: 'Edelsbrunner H, Fasy BT, Rote G. 2013. Add isotropic Gaussian kernels at
own risk: More and more resilient modes in higher dimensions. Discrete & Computational
Geometry. 49(4), 797–822.'
mla: 'Edelsbrunner, Herbert, et al. “Add Isotropic Gaussian Kernels at Own Risk:
More and More Resilient Modes in Higher Dimensions.” Discrete & Computational
Geometry, vol. 49, no. 4, Springer, 2013, pp. 797–822, doi:10.1007/s00454-013-9517-x.'
short: H. Edelsbrunner, B.T. Fasy, G. Rote, Discrete & Computational Geometry
49 (2013) 797–822.
corr_author: '1'
date_created: 2018-12-11T11:59:44Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2026-06-18T18:35:33Z
day: '01'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.1007/s00454-013-9517-x
external_id:
isi:
- '000320672400005'
intvolume: ' 49'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s00454-013-9517-x
month: '06'
oa: 1
oa_version: Published Version
page: 797 - 822
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '3991'
quality_controlled: '1'
related_material:
record:
- id: '3134'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: 'Add isotropic Gaussian kernels at own risk: More and more resilient modes
in higher dimensions'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 49
year: '2013'
...
---
OA_type: closed access
_id: '3993'
abstract:
- lang: eng
text: We present algorithms for constructing a hierarchy of increasingly coarse
Morse-Smale complexes that decompose a piecewise linear 2-manifold. While these
complexes are defined only in the smooth category, we extend the construction
to the piecewise linearcategory by ensuring structural integrity and simulating
differentiability. We then simplify Morse-Smale complexes by canceling pairs of
critical points in order of increasing persistence.
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: John
full_name: Harer, John
last_name: Harer
- first_name: Afra
full_name: Zomorodian, Afra
last_name: Zomorodian
citation:
ama: Edelsbrunner H, Harer J, Zomorodian A. Hierarchical Morse-Smale complexes for
piecewise linear 2-manifolds. Discrete & Computational Geometry. 2003;30:87-107.
doi:10.1007/s00454-003-2926-5
apa: Edelsbrunner, H., Harer, J., & Zomorodian, A. (2003). Hierarchical Morse-Smale
complexes for piecewise linear 2-manifolds. Discrete & Computational Geometry.
Springer nature. https://doi.org/10.1007/s00454-003-2926-5
chicago: Edelsbrunner, Herbert, John Harer, and Afra Zomorodian. “Hierarchical Morse-Smale
Complexes for Piecewise Linear 2-Manifolds.” Discrete & Computational Geometry.
Springer nature, 2003. https://doi.org/10.1007/s00454-003-2926-5.
ieee: H. Edelsbrunner, J. Harer, and A. Zomorodian, “Hierarchical Morse-Smale complexes
for piecewise linear 2-manifolds,” Discrete & Computational Geometry,
vol. 30. Springer nature, pp. 87–107, 2003.
ista: Edelsbrunner H, Harer J, Zomorodian A. 2003. Hierarchical Morse-Smale complexes
for piecewise linear 2-manifolds. Discrete & Computational Geometry. 30, 87–107.
mla: Edelsbrunner, Herbert, et al. “Hierarchical Morse-Smale Complexes for Piecewise
Linear 2-Manifolds.” Discrete & Computational Geometry, vol. 30, Springer
nature, 2003, pp. 87–107, doi:10.1007/s00454-003-2926-5.
short: H. Edelsbrunner, J. Harer, A. Zomorodian, Discrete & Computational Geometry
30 (2003) 87–107.
date_created: 2018-12-11T12:06:19Z
date_published: 2003-05-01T00:00:00Z
date_updated: 2026-05-06T08:08:23Z
day: '01'
doi: 10.1007/s00454-003-2926-5
extern: '1'
intvolume: ' 30'
language:
- iso: eng
month: '05'
oa_version: None
page: 87 - 107
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issnl:
- 0179-5376
publication_status: published
publisher: Springer nature
publist_id: '2134'
quality_controlled: '1'
status: public
title: Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 30
year: '2003'
...
---
_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}>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. Discrete & Computational Geometry.
1991;6(1):407-422. doi:10.1007/BF02574698
apa: Agarwal, P., Edelsbrunner, H., Schwarzkopf, O., & Welzl, E. (1991). Euclidean
minimum spanning trees and bichromatic closest pairs. Discrete & Computational
Geometry. Springer. https://doi.org/10.1007/BF02574698
chicago: Agarwal, Pankaj, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl.
“Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” Discrete
& Computational Geometry. Springer, 1991. https://doi.org/10.1007/BF02574698.
ieee: P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, “Euclidean minimum
spanning trees and bichromatic closest pairs,” Discrete & Computational
Geometry, 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 & Computational Geometry.
6(1), 407–422.
mla: Agarwal, Pankaj, et al. “Euclidean Minimum Spanning Trees and Bichromatic Closest
Pairs.” Discrete & Computational Geometry, vol. 6, no. 1, Springer,
1991, pp. 407–22, doi:10.1007/BF02574698.
short: P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, Discrete & 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. Discrete & Computational
Geometry. 1991;6(1):435-442. doi:10.1007/BF02574700
apa: 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
& Computational Geometry. Springer. https://doi.org/10.1007/BF02574700
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.” Discrete & Computational Geometry. Springer, 1991.
https://doi.org/10.1007/BF02574700.
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,” Discrete &
Computational Geometry, 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 &
Computational Geometry. 6(1), 435–442.
mla: Aronov, Boris, et al. “Points and Triangles in the Plane and Halving Planes
in Space.” Discrete & Computational Geometry, vol. 6, no. 1, Springer,
1991, pp. 435–42, doi:10.1007/BF02574700.
short: B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, R. Wenger,
Discrete & 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>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>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>0. (v) The maximum
number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an
arrangement ofn hyperplanes ind dimensions,d>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. Discrete & Computational Geometry.
1990;5(1):197-216. doi:10.1007/BF02187785
apa: Edelsbrunner, H., Guibas, L., & Sharir, M. (1990). The complexity of many
cells in arrangements of planes and related problems. Discrete & Computational
Geometry. Springer. https://doi.org/10.1007/BF02187785
chicago: Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity
of Many Cells in Arrangements of Planes and Related Problems.” Discrete &
Computational Geometry. Springer, 1990. https://doi.org/10.1007/BF02187785.
ieee: H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity of many cells in
arrangements of planes and related problems,” Discrete & Computational
Geometry, 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 & Computational Geometry.
5(1), 197–216.
mla: Edelsbrunner, Herbert, et al. “The Complexity of Many Cells in Arrangements
of Planes and Related Problems.” Discrete & Computational Geometry,
vol. 5, no. 1, Springer, 1990, pp. 197–216, doi:10.1007/BF02187785.
short: H. Edelsbrunner, L. Guibas, M. Sharir, Discrete & 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. Discrete & Computational Geometry. 1990;5(1):35-42.
doi:10.1007/BF02187778
apa: Edelsbrunner, H., & Sharir, M. (1990). The maximum number of ways to stabn
convex nonintersecting sets in the plane is 2n−2. Discrete & Computational
Geometry. Springer. https://doi.org/10.1007/BF02187778
chicago: Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to
Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” Discrete & Computational
Geometry. Springer, 1990. https://doi.org/10.1007/BF02187778.
ieee: H. Edelsbrunner and M. Sharir, “The maximum number of ways to stabn convex
nonintersecting sets in the plane is 2n−2,” Discrete & Computational Geometry,
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 & 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.” Discrete & Computational
Geometry, vol. 5, no. 1, Springer, 1990, pp. 35–42, doi:10.1007/BF02187778.
short: H. Edelsbrunner, M. Sharir, Discrete & 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>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>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. Discrete & Computational
Geometry. 1990;5(1):161-196. doi:10.1007/BF02187784
apa: Edelsbrunner, H., Guibas, L., & Sharir, M. (1990). The complexity and construction
of many faces in arrangements of lines and of segments. Discrete & Computational
Geometry. Springer. https://doi.org/10.1007/BF02187784
chicago: Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity
and Construction of Many Faces in Arrangements of Lines and of Segments.” Discrete
& Computational Geometry. Springer, 1990. https://doi.org/10.1007/BF02187784.
ieee: H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity and construction
of many faces in arrangements of lines and of segments,” Discrete & Computational
Geometry, 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 & 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.” Discrete & Computational Geometry,
vol. 5, no. 1, Springer, 1990, pp. 161–96, doi:10.1007/BF02187784.
short: H. Edelsbrunner, L. Guibas, M. Sharir, Discrete & 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. Discrete & Computational
Geometry. 1990;5(1):99-160. doi:10.1007/BF02187783
apa: Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., & Welzl, E. (1990).
Combinatorial complexity bounds for arrangements of curves and spheres. Discrete
& Computational Geometry. Springer. https://doi.org/10.1007/BF02187783
chicago: Clarkson, Kenneth, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir,
and Emo Welzl. “Combinatorial Complexity Bounds for Arrangements of Curves and
Spheres.” Discrete & Computational Geometry. Springer, 1990. https://doi.org/10.1007/BF02187783.
ieee: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, “Combinatorial
complexity bounds for arrangements of curves and spheres,” Discrete & Computational
Geometry, 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 & Computational
Geometry. 5(1), 99–160.
mla: Clarkson, Kenneth, et al. “Combinatorial Complexity Bounds for Arrangements
of Curves and Spheres.” Discrete & Computational Geometry, vol. 5,
no. 1, Springer, 1990, pp. 99–160, doi:10.1007/BF02187783.
short: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Discrete &
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. Discrete & Computational Geometry.
1989;4(1):311-336. doi:10.1007/BF02187733'
apa: 'Edelsbrunner, H., Guibas, L., & Sharir, M. (1989). The upper envelope
of piecewise linear functions: Algorithms and applications. Discrete &
Computational Geometry. Springer. https://doi.org/10.1007/BF02187733'
chicago: 'Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Upper Envelope
of Piecewise Linear Functions: Algorithms and Applications.” Discrete &
Computational Geometry. Springer, 1989. https://doi.org/10.1007/BF02187733.'
ieee: 'H. Edelsbrunner, L. Guibas, and M. Sharir, “The upper envelope of piecewise
linear functions: Algorithms and applications,” Discrete & Computational
Geometry, 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 & Computational Geometry.
4(1), 311–336.'
mla: 'Edelsbrunner, Herbert, et al. “The Upper Envelope of Piecewise Linear Functions:
Algorithms and Applications.” Discrete & Computational Geometry, vol.
4, no. 1, Springer, 1989, pp. 311–36, doi:10.1007/BF02187733.'
short: H. Edelsbrunner, L. Guibas, M. Sharir, Discrete & 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 . Discrete & Computational Geometry. 1989;4(4):337-343.
doi:10.1007/BF02187734'
apa: 'Edelsbrunner, H. (1989). The upper envelope of piecewise linear functions:
Tight bounds on the number of faces . Discrete & Computational Geometry.
Springer. https://doi.org/10.1007/BF02187734'
chicago: 'Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions:
Tight Bounds on the Number of Faces .” Discrete & Computational Geometry.
Springer, 1989. https://doi.org/10.1007/BF02187734.'
ieee: 'H. Edelsbrunner, “The upper envelope of piecewise linear functions: Tight
bounds on the number of faces ,” Discrete & Computational Geometry,
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 & Computational Geometry. 4(4), 337–343.'
mla: 'Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions:
Tight Bounds on the Number of Faces .” Discrete & Computational Geometry,
vol. 4, no. 4, Springer, 1989, pp. 337–43, doi:10.1007/BF02187734.'
short: H. Edelsbrunner, Discrete & 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'
...
---
_id: '4088'
abstract:
- lang: eng
text: 'Anarrangement ofn lines (or line segments) in the plane is the partition
of the plane defined by these objects. Such an arrangement consists ofO(n 2) regions,
calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly,
using subquadratic space and preprocessing, so that, given any query pointp, we
can calculate efficiently the face containingp. First, we consider the case of
lines and show that with (n) space1 and (n 3/2) preprocessing time, we can answer
face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved
with high probability.) In the process, we solve three interesting subproblems:
(1) given a set ofn points, find a straight-edge spanning tree of these points
such that any line intersects only a few edges of the tree, (2) given a simple
polygonal path , form a data structure from which we can find the convex hull
of any subpath of quickly, and (3) given a set of points, organize them so that
the convex hull of their subset lying above a query line can be found quickly.
Second, using random sampling, we give a tradeoff between increasing space and
decreasing query time. Third, we extend our structure to report faces in an arrangement
of line segments in (n 1/3)+O(K) time, given(n 4/3) space and (n 5/3) preprocessing
time. Lastly, we note that our techniques allow us to computem faces in an arrangement
ofn lines in time (m 2/3 n 2/3+n), which is nearly optimal.'
acknowledgement: The first author is pleased to acknowledge the support of Amoco Fnd.
Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565.
Work on this paper by the fifth author has been supported by Office of Naval Research
Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085, by
grants from the Digital Equipment Corporation, and the IBM Corporation, and by a
research grant from the NCRD—the Israeli National Council for Research and Development.
The sixth author was supported in part by a National Science Foundation Graduate
Fellowship. This work was begun while the non-DEC authors were visiting at the DEC
Systems Research Center.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: John
full_name: Hershberger, John
last_name: Hershberger
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
- first_name: Jack
full_name: Snoeyink, Jack
last_name: Snoeyink
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Edelsbrunner H, Guibas L, Hershberger J, et al. Implicitly representing arrangements
of lines or segments. Discrete & Computational Geometry. 1989;4(1):433-466.
doi:10.1007/BF02187742
apa: Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., Sharir, M., Snoeyink,
J., & Welzl, E. (1989). Implicitly representing arrangements of lines or segments.
Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187742
chicago: Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, Raimund Seidel,
Micha Sharir, Jack Snoeyink, and Emo Welzl. “Implicitly Representing Arrangements
of Lines or Segments.” Discrete & Computational Geometry. Springer,
1989. https://doi.org/10.1007/BF02187742.
ieee: H. Edelsbrunner et al., “Implicitly representing arrangements of lines
or segments,” Discrete & Computational Geometry, vol. 4, no. 1. Springer,
pp. 433–466, 1989.
ista: Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M, Snoeyink J, Welzl
E. 1989. Implicitly representing arrangements of lines or segments. Discrete &
Computational Geometry. 4(1), 433–466.
mla: Edelsbrunner, Herbert, et al. “Implicitly Representing Arrangements of Lines
or Segments.” Discrete & Computational Geometry, vol. 4, no. 1, Springer,
1989, pp. 433–66, doi:10.1007/BF02187742.
short: H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink,
E. Welzl, Discrete & Computational Geometry 4 (1989) 433–466.
date_created: 2018-12-11T12:06:52Z
date_published: 1989-12-01T00:00:00Z
date_updated: 2022-02-10T15:03:48Z
day: '01'
doi: 10.1007/BF02187742
extern: '1'
intvolume: ' 4'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://link.springer.com/article/10.1007/BF02187742
month: '12'
oa: 1
oa_version: Published Version
page: 433 - 466
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2036'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Implicitly representing arrangements of lines or segments
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1989'
...
---
_id: '4089'
abstract:
- lang: eng
text: Motivated by a number of motion-planning questions, we investigate in this
paper some general topological and combinatorial properties of the boundary of
the union ofn regions bounded by Jordan curves in the plane. We show that, under
some fairly weak conditions, a simply connected surface can be constructed that
exactly covers this union and whose boundary has combinatorial complexity that
is nearly linear, even though the covered region can have quadratic complexity.
In the case where our regions are delimited by Jordan acrs in the upper halfplane
starting and ending on thex-axis such that any pair of arcs intersect in at most
three points, we prove that the total number of subarcs that appear on the boundary
of the union is only (n(n)), where(n) is the extremely slowly growing functional
inverse of Ackermann's function.
acknowledgement: The first author is pleased to acknowledge the support of Amoco Fnd.
Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565.
Work on this paper by the fourth and seventh authors has been supported by Office
of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085,
and by grants from the Digital Equipment Corporation and the IBM Corporation. The
seventh author in addition wishes to acknowledge support by a research grant from
the NCRD—the Israeli National Council for Research and Development. The fifth author
would like to acknowledge support in part by NSF grant DMS-8501947. Finally, the
eighth author was supported in part by a National Science Foundation Graduate Fellowship.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: John
full_name: Hershberger, John
last_name: Hershberger
- first_name: János
full_name: Pach, János
last_name: Pach
- first_name: Richard
full_name: Pollack, Richard
last_name: Pollack
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
- first_name: Jack
full_name: Snoeyink, Jack
last_name: Snoeyink
citation:
ama: Edelsbrunner H, Guibas L, Hershberger J, et al. On arrangements of Jordan arcs
with three intersections per pair. Discrete & Computational Geometry.
1989;4(1):523-539. doi:10.1007/BF02187745
apa: Edelsbrunner, H., Guibas, L., Hershberger, J., Pach, J., Pollack, R., Seidel,
R., … Snoeyink, J. (1989). On arrangements of Jordan arcs with three intersections
per pair. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187745
chicago: Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, János Pach, Richard
Pollack, Raimund Seidel, Micha Sharir, and Jack Snoeyink. “On Arrangements of
Jordan Arcs with Three Intersections per Pair.” Discrete & Computational
Geometry. Springer, 1989. https://doi.org/10.1007/BF02187745.
ieee: H. Edelsbrunner et al., “On arrangements of Jordan arcs with three
intersections per pair,” Discrete & Computational Geometry, vol. 4,
no. 1. Springer, pp. 523–539, 1989.
ista: Edelsbrunner H, Guibas L, Hershberger J, Pach J, Pollack R, Seidel R, Sharir
M, Snoeyink J. 1989. On arrangements of Jordan arcs with three intersections per
pair. Discrete & Computational Geometry. 4(1), 523–539.
mla: Edelsbrunner, Herbert, et al. “On Arrangements of Jordan Arcs with Three Intersections
per Pair.” Discrete & Computational Geometry, vol. 4, no. 1, Springer,
1989, pp. 523–39, doi:10.1007/BF02187745.
short: H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel,
M. Sharir, J. Snoeyink, Discrete & Computational Geometry 4 (1989) 523–539.
date_created: 2018-12-11T12:06:52Z
date_published: 1989-12-01T00:00:00Z
date_updated: 2022-02-10T15:40:04Z
day: '01'
doi: 10.1007/BF02187745
extern: '1'
intvolume: ' 4'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://link.springer.com/article/10.1007/BF02187745
month: '12'
oa: 1
oa_version: Published Version
page: 523 - 539
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2037'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On arrangements of Jordan arcs with three intersections per pair
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1989'
...
---
_id: '4093'
abstract:
- lang: eng
text: This paper investigates the combinatorial and computational aspects of certain
extremal geometric problems in two and three dimensions. Specifically, we examine
the problem of intersecting a convex subdivision with a line in order to maximize
the number of intersections. A similar problem is to maximize the number of intersected
facets in a cross-section of a three-dimensional convex polytope. Related problems
concern maximum chains in certain families of posets defined over the regions
of a convex subdivision. In most cases we are able to prove sharp bounds on the
asymptotic behavior of the corresponding extremal functions. We also describe
polynomial algorithms for all the problems discussed.
acknowledgement: "Bernard Chazelle wishes to acknowledge the National Science Foundation
for supporting this research in part under Grant No. MCS83-03925. Herbert Edelsbrunner
is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862.
We wish to thank J. Pach and E. Szemeredi for valuable discussions on several\r\nof
the problems studied in this paper."
article_processing_charge: No
author:
- first_name: Bernard
full_name: Chazelle, Bernard
last_name: Chazelle
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
citation:
ama: Chazelle B, Edelsbrunner H, Guibas L. The complexity of cutting complexes.
Discrete & Computational Geometry. 1989;4(1):139-181. doi:10.1007/BF02187720
apa: Chazelle, B., Edelsbrunner, H., & Guibas, L. (1989). The complexity of
cutting complexes. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187720
chicago: Chazelle, Bernard, Herbert Edelsbrunner, and Leonidas Guibas. “The Complexity
of Cutting Complexes.” Discrete & Computational Geometry. Springer,
1989. https://doi.org/10.1007/BF02187720.
ieee: B. Chazelle, H. Edelsbrunner, and L. Guibas, “The complexity of cutting complexes,”
Discrete & Computational Geometry, vol. 4, no. 1. Springer, pp. 139–181,
1989.
ista: Chazelle B, Edelsbrunner H, Guibas L. 1989. The complexity of cutting complexes.
Discrete & Computational Geometry. 4(1), 139–181.
mla: Chazelle, Bernard, et al. “The Complexity of Cutting Complexes.” Discrete
& Computational Geometry, vol. 4, no. 1, Springer, 1989, pp. 139–81, doi:10.1007/BF02187720.
short: B. Chazelle, H. Edelsbrunner, L. Guibas, Discrete & Computational Geometry
4 (1989) 139–181.
date_created: 2018-12-11T12:06:54Z
date_published: 1989-03-01T00:00:00Z
date_updated: 2022-02-10T10:25:57Z
day: '01'
doi: 10.1007/BF02187720
extern: '1'
intvolume: ' 4'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187720
month: '03'
oa_version: None
page: 139 - 181
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2032'
quality_controlled: '1'
status: public
title: The complexity of cutting complexes
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1989'
...
---
_id: '4100'
abstract:
- lang: eng
text: "This paper investigates the existence of linear space data structures for
range searching. We examine thehomothetic range search problem, where a setS ofn
points in the plane is to be preprocessed so that for any triangleT with sides
parallel to three fixed directions the points ofS that lie inT can be computed
efficiently. We also look atdomination searching in three dimensions. In this
problem,S is a set ofn points inE 3 and the question is to retrieve all points
ofS that are dominated by some query point. We describe linear space data structures
for both problems. The query time is optimal in the first case and nearly optimal
in the second.\r\n"
acknowledgement: This research was conducted while the first author was with Brown
University and the second author was with the Technical University of Graz, Austria.
The first author was supported in part by NSF Grant MCS 83-03925.
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
full_name: Chazelle, Bernard
last_name: Chazelle
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Chazelle B, Edelsbrunner H. Linear space data structures for two types of range
search. Discrete & Computational Geometry. 1987;2(1):113-126. doi:10.1007/BF02187875
apa: Chazelle, B., & Edelsbrunner, H. (1987). Linear space data structures for
two types of range search. Discrete & Computational Geometry. Springer.
https://doi.org/10.1007/BF02187875
chicago: Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures
for Two Types of Range Search.” Discrete & Computational Geometry.
Springer, 1987. https://doi.org/10.1007/BF02187875.
ieee: B. Chazelle and H. Edelsbrunner, “Linear space data structures for two types
of range search,” Discrete & Computational Geometry, vol. 2, no. 1.
Springer, pp. 113–126, 1987.
ista: Chazelle B, Edelsbrunner H. 1987. Linear space data structures for two types
of range search. Discrete & Computational Geometry. 2(1), 113–126.
mla: Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures
for Two Types of Range Search.” Discrete & Computational Geometry,
vol. 2, no. 1, Springer, 1987, pp. 113–26, doi:10.1007/BF02187875.
short: B. Chazelle, H. Edelsbrunner, Discrete & Computational Geometry 2 (1987)
113–126.
date_created: 2018-12-11T12:06:56Z
date_published: 1987-01-01T00:00:00Z
date_updated: 2022-02-03T11:07:26Z
day: '01'
doi: 10.1007/BF02187875
extern: '1'
intvolume: ' 2'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 113 - 126
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2022'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Linear space data structures for two types of range search
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2
year: '1987'
...
---
_id: '4108'
abstract:
- lang: eng
text: We propose a uniform and general framework for defining and dealing with Voronoi
diagrams. In this framework a Voronoi diagram is a partition of a domainD induced
by a finite number of real valued functions onD. Valuable insight can be gained
when one considers how these real valued functions partitionD ×R. With this view
it turns out that the standard Euclidean Voronoi diagram of point sets inR d along
with its order-k generalizations are intimately related to certain arrangements
of hyperplanes. This fact can be used to obtain new Voronoi diagram algorithms.
We also discuss how the formalism of arrangements can be used to solve certain
intersection and union problems.
acknowledgement: 'We would like to thank John Gilbert for his careful reading of the
manuscript and his many suggestions for improvement. We also want to thank Bennett
Battaile, Gianfranco Bilardi, Joseph O''Rourke, and Chee Yap for their comments. '
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
citation:
ama: Edelsbrunner H, Seidel R. Voronoi diagrams and arrangements. Discrete &
Computational Geometry. 1986;1(1):25-44. doi:10.1007/BF02187681
apa: Edelsbrunner, H., & Seidel, R. (1986). Voronoi diagrams and arrangements.
Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187681
chicago: Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.”
Discrete & Computational Geometry. Springer, 1986. https://doi.org/10.1007/BF02187681.
ieee: H. Edelsbrunner and R. Seidel, “Voronoi diagrams and arrangements,” Discrete
& Computational Geometry, vol. 1, no. 1. Springer, pp. 25–44, 1986.
ista: Edelsbrunner H, Seidel R. 1986. Voronoi diagrams and arrangements. Discrete
& Computational Geometry. 1(1), 25–44.
mla: Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.”
Discrete & Computational Geometry, vol. 1, no. 1, Springer, 1986, pp.
25–44, doi:10.1007/BF02187681.
short: H. Edelsbrunner, R. Seidel, Discrete & Computational Geometry 1 (1986)
25–44.
date_created: 2018-12-11T12:06:59Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T08:53:39Z
day: '01'
doi: 10.1007/BF02187681
extern: '1'
intvolume: ' 1'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 25 - 44
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2012'
quality_controlled: '1'
status: public
title: Voronoi diagrams and arrangements
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1986'
...