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

Producción científica: Conference contribution › revisión exhaustiva

2 Citas (Scopus)

Resumen

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.

Idioma original	English
Título de la publicación alojada	Mathematical Foundations of Computer Science 1984 - Proceedings, 11th Symposium
Editores	Michael P. Chytil, Vaclav Koubek
Páginas	339-347
Número de páginas	9
DOI	https://doi.org/10.1007/BFb0030315
Estado	Published - 1984
Evento	11th Symposium on Mathematical Foundations of Computer Science, MFCS 1984 - Praha, Serbia Duración: sept 3 1984 → sept 7 1984

Serie de la publicación

Nombre	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen	176 LNCS
ISSN (versión impresa)	0302-9743
ISSN (versión digital)	1611-3349

Conference

Conference	11th Symposium on Mathematical Foundations of Computer Science, MFCS 1984
País/Territorio	Serbia
Ciudad	Praha
Período	9/3/84 → 9/7/84

Nota bibliográfica

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Acceder al documento

10.1007/BFb0030315

Otros archivos y enlaces

Citar esto

Jaromczyk, J. W. (1984). Lower bounds for polygon simplicity testing and other problems. En 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. En 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).

Producción científica: Conference contribution › revisión exhaustiva

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 -

Jaromczyk JW. Lower bounds for polygon simplicity testing and other problems. En Chytil MP, Koubek V, editores, Mathematical Foundations of Computer Science 1984 - Proceedings, 11th Symposium. 1984. p. 339-347. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0030315

Lower bounds for polygon simplicity testing and other problems

Resumen

Serie de la publicación

Conference

Nota bibliográfica

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto