3 Search Results for "Arseneva, Elena"

Document
DOI: 10.4230/LIPIcs.SoCG.2023.52
Abstract Voronoi-Like Graphs: Extending Delaunay’s Theorem and Applications

Authors: Evanthia Papadopoulou

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Any system of bisectors (in the sense of abstract Voronoi diagrams) defines an arrangement of simple curves in the plane. We define Voronoi-like graphs on such an arrangement, which are graphs whose vertices are locally Voronoi. A vertex v is called locally Voronoi, if v and its incident edges appear in the Voronoi diagram of three sites. In a so-called admissible bisector system, where Voronoi regions are connected and cover the plane, we prove that any Voronoi-like graph is indeed an abstract Voronoi diagram. The result can be seen as an abstract dual version of Delaunay’s theorem on (locally) empty circles. Further, we define Voronoi-like cycles in an admissible bisector system, and show that the Voronoi-like graph induced by such a cycle C is a unique tree (or a forest, if C is unbounded). In the special case where C is the boundary of an abstract Voronoi region, the induced Voronoi-like graph can be computed in expected linear time following the technique of [Junginger and Papadopoulou SOCG'18]. Otherwise, within the same time, the algorithm constructs the Voronoi-like graph of a cycle C′ on the same set (or subset) of sites, which may equal C or be enclosed by C. Overall, the technique computes abstract Voronoi (or Voronoi-like) trees and forests in linear expected time, given the order of their leaves along a Voronoi-like cycle. We show a direct application in updating a constraint Delaunay triangulation in linear expected time, after the insertion of a new segment constraint, simplifying upon the result of [Shewchuk and Brown CGTA 2015].
Cite as

Evanthia Papadopoulou. Abstract Voronoi-Like Graphs: Extending Delaunay’s Theorem and Applications. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{papadopoulou:LIPIcs.SoCG.2023.52,
  author =	{Papadopoulou, Evanthia},
  title =	{{Abstract Voronoi-Like Graphs: Extending Delaunay’s Theorem and Applications}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{52:1--52:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.52},
  URN =		{urn:nbn:de:0030-drops-179024},
  doi =		{10.4230/LIPIcs.SoCG.2023.52},
  annote =	{Keywords: Voronoi-like graph, abstract Voronoi diagram, Delaunay’s theorem, Voronoi tree, linear-time randomized algorithm, constraint Delaunay triangulation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.11
Adjacency Graphs of Polyhedral Surfaces

Authors: Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in ℝ³. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains K_5, K_{5,81}, or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, K_{4,4}, and K_{3,5} can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (1983), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in Ω(n log n). From the non-realizability of K_{5,81}, we obtain that any realizable n-vertex graph has 𝒪(n^{9/5}) edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.
Cite as

Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff. Adjacency Graphs of Polyhedral Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arseneva_et_al:LIPIcs.SoCG.2021.11,
  author =	{Arseneva, Elena and Kleist, Linda and Klemz, Boris and L\"{o}ffler, Maarten and Schulz, Andr\'{e} and Vogtenhuber, Birgit and Wolff, Alexander},
  title =	{{Adjacency Graphs of Polyhedral Surfaces}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.11},
  URN =		{urn:nbn:de:0030-drops-138107},
  doi =		{10.4230/LIPIcs.SoCG.2021.11},
  annote =	{Keywords: polyhedral complexes, realizability, contact representation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.58
Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain

Authors: Elena Arseneva, Man-Kwun Chiu, Matias Korman, Aleksandar Markovic, Yoshio Okamoto, Aurélien Ooms, André van Renssen, and Marcel Roeloffzen

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O(min(n^omega, n^2 + nh log h + chi^2)) time, where omega<2.373 denotes the matrix multiplication exponent and chi in Omega(n) cap O(n^2) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O(n^2 log n) time.
Cite as

Elena Arseneva, Man-Kwun Chiu, Matias Korman, Aleksandar Markovic, Yoshio Okamoto, Aurélien Ooms, André van Renssen, and Marcel Roeloffzen. Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{arseneva_et_al:LIPIcs.ISAAC.2018.58,
  author =	{Arseneva, Elena and Chiu, Man-Kwun and Korman, Matias and Markovic, Aleksandar and Okamoto, Yoshio and Ooms, Aur\'{e}lien and van Renssen, Andr\'{e} and Roeloffzen, Marcel},
  title =	{{Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{58:1--58:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.58},
  URN =		{urn:nbn:de:0030-drops-100060},
  doi =		{10.4230/LIPIcs.ISAAC.2018.58},
  annote =	{Keywords: Rectilinear link distance, polygonal domain, diameter, radius}
}
  • Refine by Author
  • 2 Arseneva, Elena
  • 1 Chiu, Man-Kwun
  • 1 Kleist, Linda
  • 1 Klemz, Boris
  • 1 Korman, Matias
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Graphs and surfaces

  • Refine by Keyword
  • 1 Delaunay’s theorem
  • 1 Rectilinear link distance
  • 1 Voronoi tree
  • 1 Voronoi-like graph
  • 1 abstract Voronoi diagram
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2021
  • 1 2023

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 Imprint Privacy Contact