Search Results

Documents authored by Türkoglu, Duru

Found 2 Possible Name Variants:

Türkoglu, Duru

Document
DOI: 10.4230/LIPIcs.SoCG.2020.34
The Stretch Factor of Hexagon-Delaunay Triangulations

Authors: Michael Dennis, Ljubomir Perković, and Duru Türkoğlu

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
The problem of computing the exact stretch factor (i.e., the tight bound on the worst case stretch factor) of a Delaunay triangulation is one of the longstanding open problems in computational geometry. Over the years, a series of upper and lower bounds on the exact stretch factor have been obtained but the gap between them is still large. An alternative approach to solving the problem is to develop techniques for computing the exact stretch factor of "easier" types of Delaunay triangulations, in particular those defined using regular-polygons instead of a circle. Tight bounds exist for Delaunay triangulations defined using an equilateral triangle and a square. In this paper, we determine the exact stretch factor of Delaunay triangulations defined using a regular hexagon: It is 2. We think that the main contribution of this paper are the two techniques we have developed to compute tight upper bounds for the stretch factor of Hexagon-Delaunay triangulations.
Cite as

Michael Dennis, Ljubomir Perković, and Duru Türkoğlu. The Stretch Factor of Hexagon-Delaunay Triangulations. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dennis_et_al:LIPIcs.SoCG.2020.34,
  author =	{Dennis, Michael and Perkovi\'{c}, Ljubomir and T\"{u}rko\u{g}lu, Duru},
  title =	{{The Stretch Factor of Hexagon-Delaunay Triangulations}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.34},
  URN =		{urn:nbn:de:0030-drops-121920},
  doi =		{10.4230/LIPIcs.SoCG.2020.34},
  annote =	{Keywords: Delaunay triangulation, geometric spanner, plane spanner, stretch factor, spanning ratio}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.45
Degree Four Plane Spanners: Simpler and Better

Authors: Iyad Kanj, Ljubomir Perkovic, and Duru Türkoglu

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Let P be a set of n points embedded in the plane, and let C be the complete Euclidean graph whose point-set is P. Each edge in C between two points p, q is realized as the line segment [pq], and is assigned a weight equal to the Euclidean distance |pq|. In this paper, we show how to construct in O(nlg{n}) time a plane spanner of C of maximum degree at most 4 and of stretch factor at most 20. This improves a long sequence of results on the construction of bounded degree plane spanners of C. Our result matches the smallest known upper bound of 4 by Bonichon et al. on the maximum degree while significantly improving their stretch factor upper bound from 156.82 to 20. The construction of our spanner is based on Delaunay triangulations defined with respect to the equilateral-triangle distance, and uses a different approach than that used by Bonichon et al. Our approach leads to a simple and intuitive construction of a well-structured spanner, and reveals useful structural properties of the Delaunay triangulations defined with respect to the equilateral-triangle distance.
Cite as

Iyad Kanj, Ljubomir Perkovic, and Duru Türkoglu. Degree Four Plane Spanners: Simpler and Better. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kanj_et_al:LIPIcs.SoCG.2016.45,
  author =	{Kanj, Iyad and Perkovic, Ljubomir and T\"{u}rkoglu, Duru},
  title =	{{Degree Four Plane Spanners: Simpler and Better}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.45},
  URN =		{urn:nbn:de:0030-drops-59376},
  doi =		{10.4230/LIPIcs.SoCG.2016.45},
  annote =	{Keywords: Nonnumerical Algorithms and Problems,Computational Geometry and Object Modeling}
}

Türkoğlu, Duru

Document
DOI: 10.4230/LIPIcs.SoCG.2020.34
The Stretch Factor of Hexagon-Delaunay Triangulations

Authors: Michael Dennis, Ljubomir Perković, and Duru Türkoğlu

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
The problem of computing the exact stretch factor (i.e., the tight bound on the worst case stretch factor) of a Delaunay triangulation is one of the longstanding open problems in computational geometry. Over the years, a series of upper and lower bounds on the exact stretch factor have been obtained but the gap between them is still large. An alternative approach to solving the problem is to develop techniques for computing the exact stretch factor of "easier" types of Delaunay triangulations, in particular those defined using regular-polygons instead of a circle. Tight bounds exist for Delaunay triangulations defined using an equilateral triangle and a square. In this paper, we determine the exact stretch factor of Delaunay triangulations defined using a regular hexagon: It is 2. We think that the main contribution of this paper are the two techniques we have developed to compute tight upper bounds for the stretch factor of Hexagon-Delaunay triangulations.
Cite as

Michael Dennis, Ljubomir Perković, and Duru Türkoğlu. The Stretch Factor of Hexagon-Delaunay Triangulations. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dennis_et_al:LIPIcs.SoCG.2020.34,
  author =	{Dennis, Michael and Perkovi\'{c}, Ljubomir and T\"{u}rko\u{g}lu, Duru},
  title =	{{The Stretch Factor of Hexagon-Delaunay Triangulations}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.34},
  URN =		{urn:nbn:de:0030-drops-121920},
  doi =		{10.4230/LIPIcs.SoCG.2020.34},
  annote =	{Keywords: Delaunay triangulation, geometric spanner, plane spanner, stretch factor, spanning ratio}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.45
Degree Four Plane Spanners: Simpler and Better

Authors: Iyad Kanj, Ljubomir Perkovic, and Duru Türkoglu

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Let P be a set of n points embedded in the plane, and let C be the complete Euclidean graph whose point-set is P. Each edge in C between two points p, q is realized as the line segment [pq], and is assigned a weight equal to the Euclidean distance |pq|. In this paper, we show how to construct in O(nlg{n}) time a plane spanner of C of maximum degree at most 4 and of stretch factor at most 20. This improves a long sequence of results on the construction of bounded degree plane spanners of C. Our result matches the smallest known upper bound of 4 by Bonichon et al. on the maximum degree while significantly improving their stretch factor upper bound from 156.82 to 20. The construction of our spanner is based on Delaunay triangulations defined with respect to the equilateral-triangle distance, and uses a different approach than that used by Bonichon et al. Our approach leads to a simple and intuitive construction of a well-structured spanner, and reveals useful structural properties of the Delaunay triangulations defined with respect to the equilateral-triangle distance.
Cite as

Iyad Kanj, Ljubomir Perkovic, and Duru Türkoglu. Degree Four Plane Spanners: Simpler and Better. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kanj_et_al:LIPIcs.SoCG.2016.45,
  author =	{Kanj, Iyad and Perkovic, Ljubomir and T\"{u}rkoglu, Duru},
  title =	{{Degree Four Plane Spanners: Simpler and Better}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.45},
  URN =		{urn:nbn:de:0030-drops-59376},
  doi =		{10.4230/LIPIcs.SoCG.2016.45},
  annote =	{Keywords: Nonnumerical Algorithms and Problems,Computational Geometry and Object Modeling}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact