Paper by Erik D. Demaine

Reference:

Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, and Anak Yodpinyanee, “Dissection with the Fewest Pieces is Hard, Even to Approximate”, in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 37–48.

BibTeX

@InProceedings{Dissection_JCDCGG2015full,
  AUTHOR        = {Jeffrey Bosboom and Erik D. Demaine and Martin L. Demaine and Jayson Lynch and Pasin Manurangsi and Mikhail Rudoy and Anak Yodpinyanee},
  TITLE         = {Dissection with the Fewest Pieces is Hard, Even to Approximate},
  BOOKTITLE     = {Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015)},
  bookurl       = {http://www.kurims.kyoto-u.ac.jp/~takazawa/JCDCGG2015/},
  ADDRESS       = {Kyoto, Japan},
  MONTH         = {September 14--16},
  YEAR          = 2015,
  SERIES        = {Lecture Notes in Computer Science},
  seriesurl     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 9943,
  PAGES         = {37--48},

  doi           = {https://dx.doi.org/10.1007/978-3-319-48532-4_4},
  dblp          = {https://dblp.org/rec/conf/jcdcg/BosboomDDLMRY15},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-319-48532-4_4">SpringerLink</A> and as <A HREF="https://arXiv.org/abs/1512.06706">arXiv:1512.06706</A>.},
  replaces      = {Dissection_JCDCGG2015},
  papers        = {Dissection_JCDCGG2015},
  withstudent   = 1,
}

Abstract:

We prove that it is NP-hard to dissect one simple orthogonal polygon into another using a given number of pieces, as is approximating the fewest pieces to within a factor of 1 + 1/1080 − ε.

Comments:

This paper is also available from SpringerLink and as arXiv:1512.06706.

Availability:

The paper is available in PDF (367k).

See information on file formats.

[Google Scholar search]

Related papers:

Dissection_JCDCGG2015 (k-piece dissection is NP-hard)