Discretized approaches to schematization

M. Löffler; W. Meulemans

Discretized approaches to schematization

M. Löffler, W. Meulemans

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

7 Citations (Scopus)

104 Downloads (Pure)

Abstract

For both the Fréchet distance and the symmetric difference, we show that finding the simple polygon S restricted to a grid that best resembles a simple polygon P is NP-complete, even if: (1) we require that S and P have equal area; (2) we require turns to occur in a specified sequence for the Fréchet distance; (3) we permit S to have holes for the symmetric difference. Compilation copyright © 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved.

Original language	English
Title of host publication	29th Canadian Conference on Computational Geometry (CCCG)
Pages	220-225
Number of pages	6
Publication status	Published - 2017
Event	29th Canadian Conference on Computational Geometry (CCCG 2017) - Ottawa, Canada Duration: 26 Jul 2017 → 28 Jul 2017 Conference number: 29 http://2017.cccg.ca/

Conference

Conference	29th Canadian Conference on Computational Geometry (CCCG 2017)
Abbreviated title	CCCG 2017
Country/Territory	Canada
City	Ottawa
Period	26/07/17 → 28/07/17
Internet address	http://2017.cccg.ca/

Access to Document

publishers versionFinal published version, 393 KB

Cite this

@inproceedings{b4706896328d4c6385f816f5833ac3d0,

title = "Discretized approaches to schematization",

abstract = "For both the Fr{\'e}chet distance and the symmetric difference, we show that finding the simple polygon S restricted to a grid that best resembles a simple polygon P is NP-complete, even if: (1) we require that S and P have equal area; (2) we require turns to occur in a specified sequence for the Fr{\'e}chet distance; (3) we permit S to have holes for the symmetric difference. Compilation copyright {\textcopyright} 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved.",

author = "M. L{\"o}ffler and W. Meulemans",

year = "2017",

language = "English",

pages = "220--225",

booktitle = "29th Canadian Conference on Computational Geometry (CCCG)",

note = "29th Canadian Conference on Computational Geometry (CCCG 2017), CCCG 2017 ; Conference date: 26-07-2017 Through 28-07-2017",

url = "http://2017.cccg.ca/",

}

TY - GEN

T1 - Discretized approaches to schematization

AU - Löffler, M.

AU - Meulemans, W.

N1 - Conference code: 29

PY - 2017

Y1 - 2017

N2 - For both the Fréchet distance and the symmetric difference, we show that finding the simple polygon S restricted to a grid that best resembles a simple polygon P is NP-complete, even if: (1) we require that S and P have equal area; (2) we require turns to occur in a specified sequence for the Fréchet distance; (3) we permit S to have holes for the symmetric difference. Compilation copyright © 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved.

AB - For both the Fréchet distance and the symmetric difference, we show that finding the simple polygon S restricted to a grid that best resembles a simple polygon P is NP-complete, even if: (1) we require that S and P have equal area; (2) we require turns to occur in a specified sequence for the Fréchet distance; (3) we permit S to have holes for the symmetric difference. Compilation copyright © 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved.

UR - http://www.scopus.com/inward/record.url?scp=85072843618&partnerID=8YFLogxK

M3 - Conference contribution

SP - 220

EP - 225

BT - 29th Canadian Conference on Computational Geometry (CCCG)

T2 - 29th Canadian Conference on Computational Geometry (CCCG 2017)

Y2 - 26 July 2017 through 28 July 2017

ER -

Discretized approaches to schematization

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this