---
_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).'
date_created: 2020-08-30T22:01:09Z
date_published: 2021-02-01T00:00:00Z
date_updated: 2023-08-04T10:57:42Z
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: The Wittgenstein Prize
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
  issn:
  - '09257721'
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
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
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: 2023-09-27T12:15:16Z
day: '01'
department:
- _id: UlWa
doi: 10.1016/j.comgeo.2017.07.002
ec_funded: 1
external_id:
  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:
  - '09257721'
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 66
year: '2017'
...