---
OA_place: repository
OA_type: green
_id: '21253'
abstract:
- lang: eng
  text: We solve a problem of Dujmović and Wood (2007) by showing that a complete
    convex geometric graph on n vertices cannot be decomposed into fewer than n -
    1 star-forests, each consisting of noncrossing edges. This bound is clearly tight.
    We also discuss similar questions for abstract graphs.
acknowledgement: A preliminary version of this note has been published in the proceedings
  of the 31st International Symposium on Graph Drawing and Network Visualization,
  Palermo, 2023. The authors would like to thank the anonymous referees for their
  valuable comments.
article_number: '102186'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: János
  full_name: Pach, János
  last_name: Pach
- first_name: Morteza
  full_name: Saghafian, Morteza
  id: f86f7148-b140-11ec-9577-95435b8df824
  last_name: Saghafian
- first_name: Patrick
  full_name: Schnider, Patrick
  last_name: Schnider
citation:
  ama: Pach J, Saghafian M, Schnider P. Decomposition of geometric graphs into star-forests.
    <i>Computational Geometry</i>. 2025;129. doi:<a href="https://doi.org/10.1016/j.comgeo.2025.102186">10.1016/j.comgeo.2025.102186</a>
  apa: Pach, J., Saghafian, M., &#38; Schnider, P. (2025). Decomposition of geometric
    graphs into star-forests. <i>Computational Geometry</i>. Elsevier. <a href="https://doi.org/10.1016/j.comgeo.2025.102186">https://doi.org/10.1016/j.comgeo.2025.102186</a>
  chicago: Pach, János, Morteza Saghafian, and Patrick Schnider. “Decomposition of
    Geometric Graphs into Star-Forests.” <i>Computational Geometry</i>. Elsevier,
    2025. <a href="https://doi.org/10.1016/j.comgeo.2025.102186">https://doi.org/10.1016/j.comgeo.2025.102186</a>.
  ieee: J. Pach, M. Saghafian, and P. Schnider, “Decomposition of geometric graphs
    into star-forests,” <i>Computational Geometry</i>, vol. 129. Elsevier, 2025.
  ista: Pach J, Saghafian M, Schnider P. 2025. Decomposition of geometric graphs into
    star-forests. Computational Geometry. 129, 102186.
  mla: Pach, János, et al. “Decomposition of Geometric Graphs into Star-Forests.”
    <i>Computational Geometry</i>, vol. 129, 102186, Elsevier, 2025, doi:<a href="https://doi.org/10.1016/j.comgeo.2025.102186">10.1016/j.comgeo.2025.102186</a>.
  short: J. Pach, M. Saghafian, P. Schnider, Computational Geometry 129 (2025).
corr_author: '1'
date_created: 2026-02-16T15:48:42Z
date_published: 2025-12-01T00:00:00Z
date_updated: 2026-04-16T09:12:36Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.comgeo.2025.102186
external_id:
  arxiv:
  - '2306.13201'
intvolume: '       129'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2306.13201
month: '12'
oa: 1
oa_version: Preprint
publication: Computational Geometry
publication_identifier:
  issn:
  - 0925-7721
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
  record:
  - id: '15012'
    relation: earlier_version
    status: public
status: public
title: Decomposition of geometric graphs into star-forests
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2025'
...
---
_id: '8317'
abstract:
- lang: eng
  text: When can a polyomino piece of paper be folded into a unit cube? Prior work
    studied tree-like polyominoes, but polyominoes with holes remain an intriguing
    open problem. We present sufficient conditions for a polyomino with one or several
    holes to fold into a cube, and conditions under which cube folding is impossible.
    In particular, we show that all but five special “basic” holes guarantee foldability.
acknowledgement: This research was performed in part at the 33rd Bellairs Winter Workshop
  on Computational Geometry. We thank all other participants for a fruitful atmosphere.
  H. Akitaya was supported by NSF CCF-1422311 & 1423615. Z. Masárová was partially
  funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.
article_number: '101700'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Oswin
  full_name: Aichholzer, Oswin
  last_name: Aichholzer
- first_name: Hugo A.
  full_name: Akitaya, Hugo A.
  last_name: Akitaya
- first_name: Kenneth C.
  full_name: Cheung, Kenneth C.
  last_name: Cheung
- first_name: Erik D.
  full_name: Demaine, Erik D.
  last_name: Demaine
- first_name: Martin L.
  full_name: Demaine, Martin L.
  last_name: Demaine
- first_name: Sándor P.
  full_name: Fekete, Sándor P.
  last_name: Fekete
- first_name: Linda
  full_name: Kleist, Linda
  last_name: Kleist
- first_name: Irina
  full_name: Kostitsyna, Irina
  last_name: Kostitsyna
- first_name: Maarten
  full_name: Löffler, Maarten
  last_name: Löffler
- 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: Klara
  full_name: Mundilova, Klara
  last_name: Mundilova
- first_name: Christiane
  full_name: Schmidt, Christiane
  last_name: Schmidt
citation:
  ama: 'Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes
    into a cube. <i>Computational Geometry: Theory and Applications</i>. 2021;93.
    doi:<a href="https://doi.org/10.1016/j.comgeo.2020.101700">10.1016/j.comgeo.2020.101700</a>'
  apa: 'Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M.
    L., Fekete, S. P., … Schmidt, C. (2021). Folding polyominoes with holes into a
    cube. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href="https://doi.org/10.1016/j.comgeo.2020.101700">https://doi.org/10.1016/j.comgeo.2020.101700</a>'
  chicago: 'Aichholzer, Oswin, Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine,
    Martin L. Demaine, Sándor P. Fekete, Linda Kleist, et al. “Folding Polyominoes
    with Holes into a Cube.” <i>Computational Geometry: Theory and Applications</i>.
    Elsevier, 2021. <a href="https://doi.org/10.1016/j.comgeo.2020.101700">https://doi.org/10.1016/j.comgeo.2020.101700</a>.'
  ieee: 'O. Aichholzer <i>et al.</i>, “Folding polyominoes with holes into a cube,”
    <i>Computational Geometry: Theory and Applications</i>, vol. 93. Elsevier, 2021.'
  ista: 'Aichholzer O, Akitaya HA, Cheung KC, Demaine ED, Demaine ML, Fekete SP, Kleist
    L, Kostitsyna I, Löffler M, Masárová Z, Mundilova K, Schmidt C. 2021. Folding
    polyominoes with holes into a cube. Computational Geometry: Theory and Applications.
    93, 101700.'
  mla: 'Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” <i>Computational
    Geometry: Theory and Applications</i>, vol. 93, 101700, Elsevier, 2021, doi:<a
    href="https://doi.org/10.1016/j.comgeo.2020.101700">10.1016/j.comgeo.2020.101700</a>.'
  short: 'O. Aichholzer, H.A. Akitaya, K.C. Cheung, E.D. Demaine, M.L. Demaine, S.P.
    Fekete, L. Kleist, I. Kostitsyna, M. Löffler, Z. Masárová, K. Mundilova, C. Schmidt,
    Computational Geometry: Theory and Applications 93 (2021).'
corr_author: '1'
date_created: 2020-08-30T22:01:09Z
date_published: 2021-02-01T00:00:00Z
date_updated: 2026-04-16T09:14:31Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.comgeo.2020.101700
external_id:
  arxiv:
  - '1910.09917'
  isi:
  - '000579185100004'
intvolume: '        93'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1910.09917v3
month: '02'
oa: 1
oa_version: Preprint
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z00342
  name: Mathematics, Computer Science
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
  eissn:
  - 1879-081X
  issn:
  - 0925-7721
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
  record:
  - id: '6989'
    relation: shorter_version
    status: public
scopus_import: '1'
status: public
title: Folding polyominoes with holes into a cube
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 93
year: '2021'
...
---
_id: '793'
abstract:
- lang: eng
  text: 'Let P be a finite point set in the plane. A cordinary triangle in P is a
    subset of P consisting of three non-collinear points such that each of the three
    lines determined by the three points contains at most c points of P . Motivated
    by a question of Erdös, and answering a question of de Zeeuw, we prove that there
    exists a constant c &gt; 0such that P contains a c-ordinary triangle, provided
    that P is not contained in the union of two lines. Furthermore, the number of
    c-ordinary triangles in P is Ω(| P |). '
article_processing_charge: No
arxiv: 1
author:
- first_name: Radoslav
  full_name: Fulek, Radoslav
  id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
  last_name: Fulek
  orcid: 0000-0001-8485-1774
- first_name: Hossein
  full_name: Mojarrad, Hossein
  last_name: Mojarrad
- first_name: Márton
  full_name: Naszódi, Márton
  last_name: Naszódi
- first_name: József
  full_name: Solymosi, József
  last_name: Solymosi
- first_name: Sebastian
  full_name: Stich, Sebastian
  last_name: Stich
- first_name: May
  full_name: Szedlák, May
  last_name: Szedlák
citation:
  ama: 'Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. On the existence
    of ordinary triangles. <i>Computational Geometry: Theory and Applications</i>.
    2017;66:28-31. doi:<a href="https://doi.org/10.1016/j.comgeo.2017.07.002">10.1016/j.comgeo.2017.07.002</a>'
  apa: 'Fulek, R., Mojarrad, H., Naszódi, M., Solymosi, J., Stich, S., &#38; Szedlák,
    M. (2017). On the existence of ordinary triangles. <i>Computational Geometry:
    Theory and Applications</i>. Elsevier. <a href="https://doi.org/10.1016/j.comgeo.2017.07.002">https://doi.org/10.1016/j.comgeo.2017.07.002</a>'
  chicago: 'Fulek, Radoslav, Hossein Mojarrad, Márton Naszódi, József Solymosi, Sebastian
    Stich, and May Szedlák. “On the Existence of Ordinary Triangles.” <i>Computational
    Geometry: Theory and Applications</i>. Elsevier, 2017. <a href="https://doi.org/10.1016/j.comgeo.2017.07.002">https://doi.org/10.1016/j.comgeo.2017.07.002</a>.'
  ieee: 'R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, and M. Szedlák,
    “On the existence of ordinary triangles,” <i>Computational Geometry: Theory and
    Applications</i>, vol. 66. Elsevier, pp. 28–31, 2017.'
  ista: 'Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. 2017. On
    the existence of ordinary triangles. Computational Geometry: Theory and Applications.
    66, 28–31.'
  mla: 'Fulek, Radoslav, et al. “On the Existence of Ordinary Triangles.” <i>Computational
    Geometry: Theory and Applications</i>, vol. 66, Elsevier, 2017, pp. 28–31, doi:<a
    href="https://doi.org/10.1016/j.comgeo.2017.07.002">10.1016/j.comgeo.2017.07.002</a>.'
  short: 'R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, M. Szedlák, Computational
    Geometry: Theory and Applications 66 (2017) 28–31.'
date_created: 2018-12-11T11:48:32Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2026-04-16T09:57:17Z
day: '01'
department:
- _id: UlWa
doi: 10.1016/j.comgeo.2017.07.002
ec_funded: 1
external_id:
  arxiv:
  - '1701.08183'
  isi:
  - '000412039700003'
intvolume: '        66'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1701.08183
month: '01'
oa: 1
oa_version: Submitted Version
page: 28 - 31
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '291734'
  name: International IST Postdoc Fellowship Programme
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
  issn:
  - 0925-7721
publication_status: published
publisher: Elsevier
publist_id: '6861'
quality_controlled: '1'
status: public
title: On the existence of ordinary triangles
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 66
year: '2017'
...
---
_id: '4001'
abstract:
- lang: eng
  text: 'The construction of shape spaces is studied from a mathematical and a computational
    viewpoint. A program is outlined reducing the problem to four tasks: the representation
    of geometry, the canonical deformation of geometry, the measuring of distance
    in shape space, and the selection of base shapes. The technical part of this paper
    focuses on the second task: the specification of a deformation mixing two or more
    shapes in continuously changing proportions. (C) 2001 Elsevier Science B.V All
    rights reserved.'
acknowledgement: National Science Foundation under grants CCR-96-19542 and CCR-97-12088,
  and by the Army Research Office under grant DAAG55-98-1-0177.
article_processing_charge: No
article_type: original
author:
- first_name: Ho
  full_name: Cheng, Ho
  last_name: Cheng
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Ping
  full_name: Fu, Ping
  last_name: Fu
citation:
  ama: 'Cheng H, Edelsbrunner H, Fu P. Shape space from deformation. <i>Computational
    Geometry: Theory and Applications</i>. 2001;19(2-3):191-204. doi:<a href="https://doi.org/10.1016/S0925-7721(01)00021-9">10.1016/S0925-7721(01)00021-9</a>'
  apa: 'Cheng, H., Edelsbrunner, H., &#38; Fu, P. (2001). Shape space from deformation.
    <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href="https://doi.org/10.1016/S0925-7721(01)00021-9">https://doi.org/10.1016/S0925-7721(01)00021-9</a>'
  chicago: 'Cheng, Ho, Herbert Edelsbrunner, and Ping Fu. “Shape Space from Deformation.”
    <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2001. <a href="https://doi.org/10.1016/S0925-7721(01)00021-9">https://doi.org/10.1016/S0925-7721(01)00021-9</a>.'
  ieee: 'H. Cheng, H. Edelsbrunner, and P. Fu, “Shape space from deformation,” <i>Computational
    Geometry: Theory and Applications</i>, vol. 19, no. 2–3. Elsevier, pp. 191–204,
    2001.'
  ista: 'Cheng H, Edelsbrunner H, Fu P. 2001. Shape space from deformation. Computational
    Geometry: Theory and Applications. 19(2–3), 191–204.'
  mla: 'Cheng, Ho, et al. “Shape Space from Deformation.” <i>Computational Geometry:
    Theory and Applications</i>, vol. 19, no. 2–3, Elsevier, 2001, pp. 191–204, doi:<a
    href="https://doi.org/10.1016/S0925-7721(01)00021-9">10.1016/S0925-7721(01)00021-9</a>.'
  short: 'H. Cheng, H. Edelsbrunner, P. Fu, Computational Geometry: Theory and Applications
    19 (2001) 191–204.'
date_created: 2018-12-11T12:06:22Z
date_published: 2001-07-01T00:00:00Z
date_updated: 2023-05-10T12:57:14Z
day: '01'
doi: 10.1016/S0925-7721(01)00021-9
extern: '1'
intvolume: '        19'
issue: 2-3
language:
- iso: eng
month: '07'
oa_version: None
page: 191 - 204
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
  issn:
  - 0925-7721
publication_status: published
publisher: Elsevier
publist_id: '2123'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Shape space from deformation
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 19
year: '2001'
...
---
_id: '4002'
abstract:
- lang: eng
  text: Shape deformation refers to the continuous change of one geometric object
    to another. We develop a software tool for planning, analyzing and visualizing
    deformations between two shapes in R-2. The deformation is generated automatically
    without any user intervention or specification of feature correspondences. A unique
    property of the tool is the explicit availability of a two-dimensional shape space,
    which can be used for designing the deformation either automatically by following
    constraints and objectives or manually by drawing deformation paths.
acknowledgement: NSF under grants CCR-96-19542 and CCR-97-12088.
article_processing_charge: No
article_type: original
author:
- first_name: Siu
  full_name: Cheng, Siu
  last_name: Cheng
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Ping
  full_name: Fu, Ping
  last_name: Fu
- first_name: Ka
  full_name: Lam, Ka
  last_name: Lam
citation:
  ama: 'Cheng S, Edelsbrunner H, Fu P, Lam K. Design and analysis of planar shape
    deformation. <i>Computational Geometry: Theory and Applications</i>. 2001;19(2-3):205-218.
    doi:<a href="https://doi.org/10.1016/S0925-7721(01)00020-7">10.1016/S0925-7721(01)00020-7</a>'
  apa: 'Cheng, S., Edelsbrunner, H., Fu, P., &#38; Lam, K. (2001). Design and analysis
    of planar shape deformation. <i>Computational Geometry: Theory and Applications</i>.
    Elsevier. <a href="https://doi.org/10.1016/S0925-7721(01)00020-7">https://doi.org/10.1016/S0925-7721(01)00020-7</a>'
  chicago: 'Cheng, Siu, Herbert Edelsbrunner, Ping Fu, and Ka Lam. “Design and Analysis
    of Planar Shape Deformation.” <i>Computational Geometry: Theory and Applications</i>.
    Elsevier, 2001. <a href="https://doi.org/10.1016/S0925-7721(01)00020-7">https://doi.org/10.1016/S0925-7721(01)00020-7</a>.'
  ieee: 'S. Cheng, H. Edelsbrunner, P. Fu, and K. Lam, “Design and analysis of planar
    shape deformation,” <i>Computational Geometry: Theory and Applications</i>, vol.
    19, no. 2–3. Elsevier, pp. 205–218, 2001.'
  ista: 'Cheng S, Edelsbrunner H, Fu P, Lam K. 2001. Design and analysis of planar
    shape deformation. Computational Geometry: Theory and Applications. 19(2–3), 205–218.'
  mla: 'Cheng, Siu, et al. “Design and Analysis of Planar Shape Deformation.” <i>Computational
    Geometry: Theory and Applications</i>, vol. 19, no. 2–3, Elsevier, 2001, pp. 205–18,
    doi:<a href="https://doi.org/10.1016/S0925-7721(01)00020-7">10.1016/S0925-7721(01)00020-7</a>.'
  short: 'S. Cheng, H. Edelsbrunner, P. Fu, K. Lam, Computational Geometry: Theory
    and Applications 19 (2001) 205–218.'
date_created: 2018-12-11T12:06:22Z
date_published: 2001-07-01T00:00:00Z
date_updated: 2023-05-10T14:21:31Z
day: '01'
doi: 10.1016/S0925-7721(01)00020-7
extern: '1'
intvolume: '        19'
issue: 2-3
language:
- iso: eng
month: '07'
oa_version: None
page: 205 - 218
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
  issn:
  - 0925-7721
publication_status: published
publisher: Elsevier
publist_id: '2124'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Design and analysis of planar shape deformation
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 19
year: '2001'
...
---
_id: '4018'
abstract:
- lang: eng
  text: Given a subspace X subset of or equal to R-d and a finite set S subset of
    or equal to R-d, we introduce the Delaunay complex, D-X, restricted by X. Its
    simplices are spanned by subsets T subset of or equal to S for which the common
    intersection of Voronoi cells meets X in a non-empty set. By the nerve theorem,
    boolean OR D-X and X are homotopy equivalent if all such sets are contractible.
    This paper proves a sufficient condition for boolean OR D-X and X be homeomorphic.
acknowledgement: Partially supported by the National Science Foundation, under grant
  ASC-200301 and the Alan T. Waterman award, grant CCR-9118874.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Nimish
  full_name: Shah, Nimish
  last_name: Shah
citation:
  ama: Edelsbrunner H, Shah N. Triangulating topological spaces. <i>International
    Journal of Computational Geometry &#38; Applications</i>. 1997;7(4):365-378. doi:<a
    href="https://doi.org/10.1142/S0218195997000223">10.1142/S0218195997000223</a>
  apa: Edelsbrunner, H., &#38; Shah, N. (1997). Triangulating topological spaces.
    <i>International Journal of Computational Geometry &#38; Applications</i>. World
    Scientific Publishing. <a href="https://doi.org/10.1142/S0218195997000223">https://doi.org/10.1142/S0218195997000223</a>
  chicago: Edelsbrunner, Herbert, and Nimish Shah. “Triangulating Topological Spaces.”
    <i>International Journal of Computational Geometry &#38; Applications</i>. World
    Scientific Publishing, 1997. <a href="https://doi.org/10.1142/S0218195997000223">https://doi.org/10.1142/S0218195997000223</a>.
  ieee: H. Edelsbrunner and N. Shah, “Triangulating topological spaces,” <i>International
    Journal of Computational Geometry &#38; Applications</i>, vol. 7, no. 4. World
    Scientific Publishing, pp. 365–378, 1997.
  ista: Edelsbrunner H, Shah N. 1997. Triangulating topological spaces. International
    Journal of Computational Geometry &#38; Applications. 7(4), 365–378.
  mla: Edelsbrunner, Herbert, and Nimish Shah. “Triangulating Topological Spaces.”
    <i>International Journal of Computational Geometry &#38; Applications</i>, vol.
    7, no. 4, World Scientific Publishing, 1997, pp. 365–78, doi:<a href="https://doi.org/10.1142/S0218195997000223">10.1142/S0218195997000223</a>.
  short: H. Edelsbrunner, N. Shah, International Journal of Computational Geometry
    &#38; Applications 7 (1997) 365–378.
date_created: 2018-12-11T12:06:28Z
date_published: 1997-01-01T00:00:00Z
date_updated: 2022-08-19T08:32:23Z
day: '01'
doi: 10.1142/S0218195997000223
extern: '1'
intvolume: '         7'
issue: '4'
language:
- iso: eng
month: '01'
oa_version: None
page: 365 - 378
publication: International Journal of Computational Geometry & Applications
publication_identifier:
  issn:
  - 0925-7721
publication_status: published
publisher: World Scientific Publishing
publist_id: '2106'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Triangulating topological spaces
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 7
year: '1997'
...
---
_id: '4021'
abstract:
- lang: eng
  text: A homeomorphism from R-2 to itself distorts metric quantities, such as distance
    and area. We describe an algorithm that constructs homeomorphisms with prescribed
    area distortion. Such homeomorphisms can be used to generate cartograms, which
    are geographic maps purposely distorted so their area distributions reflects a
    variable different from area, as for example population density. The algorithm
    generates the homeomorphism through a sequence of local piecewise linear homeomorphic
    changes. Sample results produced by the preliminary implementation of the method
    are included.
acknowledgement: 'The authors thank Jack Snoeyink for bringing the cartogram problem
  to their attention, and Michael McAllister for providing pointers to the literature
  on cartograms. '
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. A combinatorial approach to cartograms. <i>Computational
    Geometry: Theory and Applications</i>. 1997;7(5-6):343-360. doi:<a href="https://doi.org/10.1016/S0925-7721(96)00006-5">10.1016/S0925-7721(96)00006-5</a>'
  apa: 'Edelsbrunner, H., &#38; Waupotitsch, R. (1997). A combinatorial approach to
    cartograms. <i>Computational Geometry: Theory and Applications</i>. Elsevier.
    <a href="https://doi.org/10.1016/S0925-7721(96)00006-5">https://doi.org/10.1016/S0925-7721(96)00006-5</a>'
  chicago: 'Edelsbrunner, Herbert, and Roman Waupotitsch. “A Combinatorial Approach
    to Cartograms.” <i>Computational Geometry: Theory and Applications</i>. Elsevier,
    1997. <a href="https://doi.org/10.1016/S0925-7721(96)00006-5">https://doi.org/10.1016/S0925-7721(96)00006-5</a>.'
  ieee: 'H. Edelsbrunner and R. Waupotitsch, “A combinatorial approach to cartograms,”
    <i>Computational Geometry: Theory and Applications</i>, vol. 7, no. 5–6. Elsevier,
    pp. 343–360, 1997.'
  ista: 'Edelsbrunner H, Waupotitsch R. 1997. A combinatorial approach to cartograms.
    Computational Geometry: Theory and Applications. 7(5–6), 343–360.'
  mla: 'Edelsbrunner, Herbert, and Roman Waupotitsch. “A Combinatorial Approach to
    Cartograms.” <i>Computational Geometry: Theory and Applications</i>, vol. 7, no.
    5–6, Elsevier, 1997, pp. 343–60, doi:<a href="https://doi.org/10.1016/S0925-7721(96)00006-5">10.1016/S0925-7721(96)00006-5</a>.'
  short: 'H. Edelsbrunner, R. Waupotitsch, Computational Geometry: Theory and Applications
    7 (1997) 343–360.'
date_created: 2018-12-11T12:06:29Z
date_published: 1997-04-01T00:00:00Z
date_updated: 2022-08-19T08:12:03Z
day: '01'
doi: 10.1016/S0925-7721(96)00006-5
extern: '1'
intvolume: '         7'
issue: 5-6
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/S0925772196000065
month: '04'
oa: 1
oa_version: Published Version
page: 343 - 360
popular_science: '1'
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
  issn:
  - 0925-7721
publication_status: published
publisher: Elsevier
publist_id: '2105'
status: public
title: A combinatorial approach to cartograms
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 7
year: '1997'
...
---
_id: '3581'
abstract:
- lang: eng
  text: 'A number of rendering algorithms in computer graphics sort three-dimensional
    objects by depth and assume that there is no cycle that makes the sorting impossible.
    One way to resolve the problem caused by cycles is to cut the objects into smaller
    pieces. In this paper we address the problem of estimating how many such cuts
    arc always sufficient. We also consider a few related algorithmic and combinatorial
    geometry problems. For example, we demonstrate that n lines in space can be sorted
    in randomized expected time O(n4’st’), provided that they define no cycle. We
    also prove an 0(n7’4) upper bound on the number of points in space so that there
    are n lines with the property that for each point there are at least three noncoplanar
    lines that contain it. '
acknowledgement: "* Bernard Chazelle wishes to acknowledge the National Science Foundation
  for supporting this research in part under Grant CCR-9002352. Herbert Edelsbrunner
  acknowledges the support of the National Science Foundation under grants CCR-8714565
  and CCR-8921421. Richard Pollack was supported in part by NSF grant CCR-8901484,
  NSA grant MDA904-89-H-2030, and DIMACS, a Science and Technology Center under NSF
  grant STC88-09648. Raimund Seidel acknowledges support by NSF grant CCR-8809040.
  Mich Sharir was partially supported by the Office of Naval\r\nResearch under Grant
  N00014-87-K-0129, by the National Science Foundation under Grant CCR-89-01484, and
  by grants from the U.S.-Israeli Binational Science Foundation and the Fund for Basic
  Research administered by the Israeli Academy of Sciences."
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
  full_name: Chazelle, Bernard
  last_name: Chazelle
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: 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: 'Chazelle B, Edelsbrunner H, Guibas L, et al. Counting and cutting cycles of
    lines and rods in space. <i>Computational Geometry: Theory and Applications</i>.
    1992;1(6):305-323. doi:<a href="https://doi.org/10.1016/0925-7721(92)90009-H">10.1016/0925-7721(92)90009-H</a>'
  apa: 'Chazelle, B., Edelsbrunner, H., Guibas, L., Pollack, R., Seidel, R., Sharir,
    M., &#38; Snoeyink, J. (1992). Counting and cutting cycles of lines and rods in
    space. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href="https://doi.org/10.1016/0925-7721(92)90009-H">https://doi.org/10.1016/0925-7721(92)90009-H</a>'
  chicago: 'Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Richard Pollack,
    Raimund Seidel, Micha Sharir, and Jack Snoeyink. “Counting and Cutting Cycles
    of Lines and Rods in Space.” <i>Computational Geometry: Theory and Applications</i>.
    Elsevier, 1992. <a href="https://doi.org/10.1016/0925-7721(92)90009-H">https://doi.org/10.1016/0925-7721(92)90009-H</a>.'
  ieee: 'B. Chazelle <i>et al.</i>, “Counting and cutting cycles of lines and rods
    in space,” <i>Computational Geometry: Theory and Applications</i>, vol. 1, no.
    6. Elsevier, pp. 305–323, 1992.'
  ista: 'Chazelle B, Edelsbrunner H, Guibas L, Pollack R, Seidel R, Sharir M, Snoeyink
    J. 1992. Counting and cutting cycles of lines and rods in space. Computational
    Geometry: Theory and Applications. 1(6), 305–323.'
  mla: 'Chazelle, Bernard, et al. “Counting and Cutting Cycles of Lines and Rods in
    Space.” <i>Computational Geometry: Theory and Applications</i>, vol. 1, no. 6,
    Elsevier, 1992, pp. 305–23, doi:<a href="https://doi.org/10.1016/0925-7721(92)90009-H">10.1016/0925-7721(92)90009-H</a>.'
  short: 'B. Chazelle, H. Edelsbrunner, L. Guibas, R. Pollack, R. Seidel, M. Sharir,
    J. Snoeyink, Computational Geometry: Theory and Applications 1 (1992) 305–323.'
date_created: 2018-12-11T12:04:04Z
date_published: 1992-06-01T00:00:00Z
date_updated: 2022-03-16T10:41:58Z
day: '01'
doi: 10.1016/0925-7721(92)90009-H
extern: '1'
intvolume: '         1'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/092577219290009H?via%3Dihub
month: '06'
oa: 1
oa_version: Published Version
page: 305 - 323
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
  issn:
  - 0925-7721
publication_status: published
publisher: Elsevier
publist_id: '2804'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counting and cutting cycles of lines and rods in space
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1992'
...