Dilation-optimal edge deletion in polygonal cycles

H.K. Ahn, M. Farshi, C. Knauer, M.H.M. Smid, Y. Wang

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

Let C be a polygonal cycle on n vertices in the plane. A randomized algorithm is presented which computes in O(n log3 n) expected time, the edge of C whose removal results in a polygonal path of smallest possible dilation. It is also shown that the edge whose removal gives a polygonal path of largest possible dilation can be computed in O(n logn) time. If C is a convex polygon, the running time for the latter problem becomes O(n). Finally, it is shown that for each edge e of C, a (1¿-¿e)-approximation to the dilation of the path C¿\¿{e} can be computed in O(n logn) total time.
Original languageEnglish
Title of host publicationProceedings of the 18th International Symposium : Algorithms and Computation (ISAAC 2007) 17-19 December 2007, Sendai, Japan
EditorsT. Tokuyama
Place of PublicationBerlin
PublisherSpringer
Pages88-99
ISBN (Print)978-3-540-77118-0
DOIs
Publication statusPublished - 2007
Event18th International Symposium on Algorithms and Computation (ISAAC 2007) - Sendai, Japan
Duration: 17 Dec 200719 Dec 2007
Conference number: 18

Publication series

NameLecture Notes in Computer Science
Volume4835
ISSN (Print)0302-9743

Conference

Conference18th International Symposium on Algorithms and Computation (ISAAC 2007)
Abbreviated titleISAAC 2007
CountryJapan
CitySendai
Period17/12/0719/12/07

Fingerprint

Dive into the research topics of 'Dilation-optimal edge deletion in polygonal cycles'. Together they form a unique fingerprint.

Cite this