Lower bounds for polygon simplicity testing and other problems

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-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 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.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 1984 - Proceedings, 11th Symposium
EditorsMichael P. Chytil, Vaclav Koubek
Pages339-347
Number of pages9
DOIs
StatePublished - 1984
Event11th Symposium on Mathematical Foundations of Computer Science, MFCS 1984 - Praha, Serbia
Duration: Sep 3 1984Sep 7 1984

Publication series

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

Conference

Conference11th Symposium on Mathematical Foundations of Computer Science, MFCS 1984
Country/TerritorySerbia
CityPraha
Period9/3/849/7/84

Bibliographical note

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'Lower bounds for polygon simplicity testing and other problems'. Together they form a unique fingerprint.

Cite this