Lower bounds for polygon simplicity testing and other problems

Jerzy W. Jaromczyk

doi:10.1007/BFb0030315

Lower bounds for polygon simplicity testing and other problems

Jerzy W. Jaromczyk

Computer Science

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

2 Scopus citations

Abstract

The new non-trivial lower bounds of time complexity for some problems of computational geometry such as: -polygon simplicity testing (computational version)-finding diameter of a set of points in R²-finding maximal distance between two sets of points in R² are derived. Some attractive geometrical constructions e.g., a curve with a constant width are used while proving the lower bounds.

Original language	English
Title of host publication	Mathematical Foundations of Computer Science 1984 - Proceedings, 11th Symposium
Editors	Michael P. Chytil, Vaclav Koubek
Pages	339-347
Number of pages	9
DOIs	https://doi.org/10.1007/BFb0030315
State	Published - 1984
Event	11th Symposium on Mathematical Foundations of Computer Science, MFCS 1984 - Praha, Serbia Duration: Sep 3 1984 → Sep 7 1984

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	176 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th Symposium on Mathematical Foundations of Computer Science, MFCS 1984
Country/Territory	Serbia
City	Praha
Period	9/3/84 → 9/7/84

Bibliographical note

Publisher Copyright:
© by Springer-Verlag Berlin Heidelberg 1984. All rights reserved.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/BFb0030315

Cite this

Jaromczyk, J. W. (1984). Lower bounds for polygon simplicity testing and other problems. In M. P. Chytil, & V. Koubek (Eds.), Mathematical Foundations of Computer Science 1984 - Proceedings, 11th Symposium (pp. 339-347). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 176 LNCS). https://doi.org/10.1007/BFb0030315

@inproceedings{f267d16c09284cf29a1282a479f21cef,

title = "Lower bounds for polygon simplicity testing and other problems",

abstract = "The new non-trivial lower bounds of time complexity for some problems of computational geometry such as: -polygon simplicity testing (computational version)-finding diameter of a set of points in R2-finding maximal distance between two sets of points in R2 are derived. Some attractive geometrical constructions e.g., a curve with a constant width are used while proving the lower bounds.",

author = "Jaromczyk, {Jerzy W.}",

note = "Publisher Copyright: {\textcopyright} by Springer-Verlag Berlin Heidelberg 1984. All rights reserved.; 11th Symposium on Mathematical Foundations of Computer Science, MFCS 1984 ; Conference date: 03-09-1984 Through 07-09-1984",

year = "1984",

doi = "10.1007/BFb0030315",

language = "English",

isbn = "9783540133728",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "339--347",

editor = "Chytil, {Michael P.} and Vaclav Koubek",

booktitle = "Mathematical Foundations of Computer Science 1984 - Proceedings, 11th Symposium",

}

Jaromczyk, JW 1984, Lower bounds for polygon simplicity testing and other problems. in MP Chytil & V Koubek (eds), Mathematical Foundations of Computer Science 1984 - Proceedings, 11th Symposium. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 176 LNCS, pp. 339-347, 11th Symposium on Mathematical Foundations of Computer Science, MFCS 1984, Praha, Serbia, 9/3/84. https://doi.org/10.1007/BFb0030315

Lower bounds for polygon simplicity testing and other problems. / Jaromczyk, Jerzy W.
Mathematical Foundations of Computer Science 1984 - Proceedings, 11th Symposium. ed. / Michael P. Chytil; Vaclav Koubek. 1984. p. 339-347 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 176 LNCS).

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

TY - GEN

T1 - Lower bounds for polygon simplicity testing and other problems

AU - Jaromczyk, Jerzy W.

PY - 1984

Y1 - 1984

N2 - The new non-trivial lower bounds of time complexity for some problems of computational geometry such as: -polygon simplicity testing (computational version)-finding diameter of a set of points in R2-finding maximal distance between two sets of points in R2 are derived. Some attractive geometrical constructions e.g., a curve with a constant width are used while proving the lower bounds.

AB - The new non-trivial lower bounds of time complexity for some problems of computational geometry such as: -polygon simplicity testing (computational version)-finding diameter of a set of points in R2-finding maximal distance between two sets of points in R2 are derived. Some attractive geometrical constructions e.g., a curve with a constant width are used while proving the lower bounds.

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

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

U2 - 10.1007/BFb0030315

DO - 10.1007/BFb0030315

M3 - Conference contribution

AN - SCOPUS:85036478498

SN - 9783540133728

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 339

EP - 347

BT - Mathematical Foundations of Computer Science 1984 - Proceedings, 11th Symposium

A2 - Chytil, Michael P.

A2 - Koubek, Vaclav

T2 - 11th Symposium on Mathematical Foundations of Computer Science, MFCS 1984

Y2 - 3 September 1984 through 7 September 1984

ER -

Lower bounds for polygon simplicity testing and other problems

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this