Dilation-optimal edge deletion in polygonal cycles

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

doi:10.1007/978-3-540-77120-3_10

Dilation-optimal edge deletion in polygonal cycles

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

Algorithms

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

4 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Titel	Proceedings of the 18th International Symposium : Algorithms and Computation (ISAAC 2007) 17-19 December 2007, Sendai, Japan
Redacteuren	T. Tokuyama
Plaats van productie	Berlin
Uitgeverij	Springer
Pagina's	88-99
ISBN van geprinte versie	978-3-540-77118-0
DOI's	https://doi.org/10.1007/978-3-540-77120-3_10
Status	Gepubliceerd - 2007
Evenement	18th International Symposium on Algorithms and Computation (ISAAC 2007) - Sendai, Japan Duur: 17 dec. 2007 → 19 dec. 2007 Congresnummer: 18

Publicatie series

Naam	Lecture Notes in Computer Science
Volume	4835
ISSN van geprinte versie	0302-9743

Congres

Congres	18th International Symposium on Algorithms and Computation (ISAAC 2007)
Verkorte titel	ISAAC 2007
Land/Regio	Japan
Stad	Sendai
Periode	17/12/07 → 19/12/07
Ander	ISAAC 2007, Sendai, Japan

Toegang tot document

10.1007/978-3-540-77120-3_10

Citeer dit

Ahn, H. K., Farshi, M., Knauer, C., Smid, M. H. M., & Wang, Y. (2007). Dilation-optimal edge deletion in polygonal cycles. In T. Tokuyama (editor), Proceedings of the 18th International Symposium : Algorithms and Computation (ISAAC 2007) 17-19 December 2007, Sendai, Japan (blz. 88-99). (Lecture Notes in Computer Science; Vol. 4835). Springer. https://doi.org/10.1007/978-3-540-77120-3_10

@inproceedings{ac66f0e4b09e477fb1cbbd2cf82a3f76,

title = "Dilation-optimal edge deletion in polygonal cycles",

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¿\textbackslash{}¿\{e\} can be computed in O(n logn) total time.",

author = "H.K. Ahn and M. Farshi and C. Knauer and M.H.M. Smid and Y. Wang",

year = "2007",

doi = "10.1007/978-3-540-77120-3\_10",

language = "English",

isbn = "978-3-540-77118-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "88--99",

editor = "T. Tokuyama",

booktitle = "Proceedings of the 18th International Symposium : Algorithms and Computation (ISAAC 2007) 17-19 December 2007, Sendai, Japan",

address = "Germany",

note = "18th International Symposium on Algorithms and Computation (ISAAC 2007), ISAAC 2007 ; Conference date: 17-12-2007 Through 19-12-2007",

}

Ahn, HK, Farshi, M, Knauer, C, Smid, MHM & Wang, Y 2007, Dilation-optimal edge deletion in polygonal cycles. in T Tokuyama (reds.), Proceedings of the 18th International Symposium : Algorithms and Computation (ISAAC 2007) 17-19 December 2007, Sendai, Japan. Lecture Notes in Computer Science, vol. 4835, Springer, Berlin, blz. 88-99, 18th International Symposium on Algorithms and Computation (ISAAC 2007), Sendai, Japan, 17/12/07. https://doi.org/10.1007/978-3-540-77120-3_10

Dilation-optimal edge deletion in polygonal cycles. / Ahn, H.K.; Farshi, M.; Knauer, C. et al.
Proceedings of the 18th International Symposium : Algorithms and Computation (ISAAC 2007) 17-19 December 2007, Sendai, Japan. reds. / T. Tokuyama. Berlin: Springer, 2007. blz. 88-99 (Lecture Notes in Computer Science; Vol. 4835).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Dilation-optimal edge deletion in polygonal cycles

AU - Ahn, H.K.

AU - Farshi, M.

AU - Knauer, C.

AU - Smid, M.H.M.

AU - Wang, Y.

N1 - Conference code: 18

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-77120-3_10

DO - 10.1007/978-3-540-77120-3_10

M3 - Conference contribution

SN - 978-3-540-77118-0

T3 - Lecture Notes in Computer Science

SP - 88

EP - 99

BT - Proceedings of the 18th International Symposium : Algorithms and Computation (ISAAC 2007) 17-19 December 2007, Sendai, Japan

A2 - Tokuyama, T.

PB - Springer

CY - Berlin

T2 - 18th International Symposium on Algorithms and Computation (ISAAC 2007)

Y2 - 17 December 2007 through 19 December 2007

ER -

Dilation-optimal edge deletion in polygonal cycles

Samenvatting

Publicatie series

Congres

Toegang tot document

Vingerafdruk

Citeer dit