6 Search Results for "Suderland, Martin"

Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2022.69
Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram (Media Exposition)

Authors: Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Given a set P of n points, the sum of distances function of a point x is d_{P}(x) : = ∑_{p ∈ P} ||x - p||. Using a subdivision approach with soft predicates we implement and visualize approximate solutions for three different problems involving the sum of distances function in ℝ². Namely, (1) finding the Fermat-Weber point, (2) constructing n-ellipses of a given set of points, and (3) constructing the nearest Voronoi diagram under the sum of distances function, given a set of point clusters as sites.
Cite as

Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap. Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 69:1-69:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mantas_et_al:LIPIcs.SoCG.2022.69,
  author =	{Mantas, Ioannis and Papadopoulou, Evanthia and Suderland, Martin and Yap, Chee},
  title =	{{Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{69:1--69:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.69},
  URN =		{urn:nbn:de:0030-drops-160773},
  doi =		{10.4230/LIPIcs.SoCG.2022.69},
  annote =	{Keywords: Fermat point, geometric median, Weber point, Fermat distance, sum of distances, n-ellipse, multifocal ellipse, min-sum Voronoi diagram, cluster Voronoi diagram}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.30
Piecewise-Linear Farthest-Site Voronoi Diagrams

Authors: Franz Aurenhammer, Evanthia Papadopoulou, and Martin Suderland

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
Voronoi diagrams induced by distance functions whose unit balls are convex polyhedra are piecewise-linear structures. Nevertheless, analyzing their combinatorial and algorithmic properties in dimensions three and higher is an intriguing problem. The situation turns easier when the farthest-site variants of such Voronoi diagrams are considered, where each site gets assigned the region of all points in space farthest from (rather than closest to) it. We give asymptotically tight upper and lower worst-case bounds on the combinatorial size of farthest-site Voronoi diagrams for convex polyhedral distance functions in general dimensions, and propose an optimal construction algorithm. Our approach is uniform in the sense that (1) it can be extended from point sites to sites that are convex polyhedra, (2) it covers the case where the distance function is additively and/or multiplicatively weighted, and (3) it allows an anisotropic scenario where each site gets allotted its particular convex distance polytope.
Cite as

Franz Aurenhammer, Evanthia Papadopoulou, and Martin Suderland. Piecewise-Linear Farthest-Site Voronoi Diagrams. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 30:1-30:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{aurenhammer_et_al:LIPIcs.ISAAC.2021.30,
  author =	{Aurenhammer, Franz and Papadopoulou, Evanthia and Suderland, Martin},
  title =	{{Piecewise-Linear Farthest-Site Voronoi Diagrams}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{30:1--30:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.30},
  URN =		{urn:nbn:de:0030-drops-154633},
  doi =		{10.4230/LIPIcs.ISAAC.2021.30},
  annote =	{Keywords: Voronoi diagram, farthest-site, polyhedral distance, polyhedral sites, general dimensions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.5
The Voronoi Diagram of Rotating Rays With applications to Floodlight Illumination

Authors: Carlos Alegría, Ioannis Mantas, Evanthia Papadopoulou, Marko Savić, Hendrik Schrezenmaier, Carlos Seara, and Martin Suderland

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We introduce the Voronoi Diagram of Rotating Rays, a Voronoi structure where the input sites are rays, and the distance function is the counterclockwise angular distance between a point and a ray-site. This novel Voronoi diagram is motivated by illumination and coverage problems, where a domain has to be covered by floodlights (wedges) of uniform angle, and the goal is to find the minimum angle necessary to cover the domain. We study the diagram in the plane, and we present structural properties, combinatorial complexity bounds, and a construction algorithm. If the rays are induced by a convex polygon, we show how to construct the ray Voronoi diagram within this polygon in linear time. Using this information, we can find in optimal linear time the Brocard angle, the minimum angle required to illuminate a convex polygon with floodlights of uniform angle. This last algorithm improves upon previous results, settling an interesting open problem.
Cite as

Carlos Alegría, Ioannis Mantas, Evanthia Papadopoulou, Marko Savić, Hendrik Schrezenmaier, Carlos Seara, and Martin Suderland. The Voronoi Diagram of Rotating Rays With applications to Floodlight Illumination. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{alegria_et_al:LIPIcs.ESA.2021.5,
  author =	{Alegr{\'\i}a, Carlos and Mantas, Ioannis and Papadopoulou, Evanthia and Savi\'{c}, Marko and Schrezenmaier, Hendrik and Seara, Carlos and Suderland, Martin},
  title =	{{The Voronoi Diagram of Rotating Rays With applications to Floodlight Illumination}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.5},
  URN =		{urn:nbn:de:0030-drops-145865},
  doi =		{10.4230/LIPIcs.ESA.2021.5},
  annote =	{Keywords: rotating rays, Voronoi diagram, oriented angular distance, Brocard angle, floodlight illumination, coverage problems, art gallery problems}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.54
Certified Approximation Algorithms for the Fermat Point and n-Ellipses

Authors: Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Given a set A of n points in ℝ^d with weight function w: A→ℝ_{> 0}, the Fermat distance function is φ(x): = ∑_{a∈A}w(a)‖x-a‖. A classic problem in facility location dating back to 1643, is to find the Fermat point x*, the point that minimizes the function φ. We consider the problem of computing a point x̃* that is an ε-approximation of x* in the sense that ‖x̃*-x*‖<ε. The algorithmic literature has so far used a different notion based on ε-approximation of the value φ(x*). We devise a certified subdivision algorithm for computing x̃*, enhanced by Newton operator techniques. We also revisit the classic Weiszfeld-Kuhn iteration scheme for x*, turning it into an ε-approximate Fermat point algorithm. Our second problem is the certified construction of ε-isotopic approximations of n-ellipses. These are the level sets φ^{-1}(r) for r > φ(x*) and d = 2. Finally, all our planar (d = 2) algorithms are implemented in order to experimentally evaluate them, using both synthetic as well as real world datasets. These experiments show the practicality of our techniques.
Cite as

Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap. Certified Approximation Algorithms for the Fermat Point and n-Ellipses. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 54:1-54:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{junginger_et_al:LIPIcs.ESA.2021.54,
  author =	{Junginger, Kolja and Mantas, Ioannis and Papadopoulou, Evanthia and Suderland, Martin and Yap, Chee},
  title =	{{Certified Approximation Algorithms for the Fermat Point and n-Ellipses}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{54:1--54:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.54},
  URN =		{urn:nbn:de:0030-drops-146359},
  doi =		{10.4230/LIPIcs.ESA.2021.54},
  annote =	{Keywords: Fermat point, n-ellipse, subdivision, approximation, certified, algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.34
Distance Bounds for High Dimensional Consistent Digital Rays and 2-D Partially-Consistent Digital Rays

Authors: Man-Kwun Chiu, Matias Korman, Martin Suderland, and Takeshi Tokuyama

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We consider the problem of digitalizing Euclidean segments. Specifically, we look for a constructive method to connect any two points in ℤ^d. The construction must be consistent (that is, satisfy the natural extension of the Euclidean axioms) while resembling them as much as possible. Previous work has shown asymptotically tight results in two dimensions with Θ(log N) error, where resemblance between segments is measured with the Hausdorff distance, and N is the L₁ distance between the two points. This construction was considered tight because of a Ω(log N) lower bound that applies to any consistent construction in ℤ². In this paper we observe that the lower bound does not directly extend to higher dimensions. We give an alternative argument showing that any consistent construction in d dimensions must have Ω(log^{1/(d-1)} N) error. We tie the error of a consistent construction in high dimensions to the error of similar weak constructions in two dimensions (constructions for which some points need not satisfy all the axioms). This not only opens the possibility for having constructions with o(log N) error in high dimensions, but also opens up an interesting line of research in the tradeoff between the number of axiom violations and the error of the construction. In order to show our lower bound, we also consider a colored variation of the concept of discrepancy of a set of points that we find of independent interest.
Cite as

Man-Kwun Chiu, Matias Korman, Martin Suderland, and Takeshi Tokuyama. Distance Bounds for High Dimensional Consistent Digital Rays and 2-D Partially-Consistent Digital Rays. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 34:1-34:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.ESA.2020.34,
  author =	{Chiu, Man-Kwun and Korman, Matias and Suderland, Martin and Tokuyama, Takeshi},
  title =	{{Distance Bounds for High Dimensional Consistent Digital Rays and 2-D Partially-Consistent Digital Rays}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{34:1--34:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.34},
  URN =		{urn:nbn:de:0030-drops-129002},
  doi =		{10.4230/LIPIcs.ESA.2020.34},
  annote =	{Keywords: Consistent Digital Line Segments, Digital Geometry, Discrepancy}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.62
Unbounded Regions of High-Order Voronoi Diagrams of Lines and Segments in Higher Dimensions

Authors: Gill Barequet, Evanthia Papadopoulou, and Martin Suderland

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We study the behavior at infinity of the farthest and the higher-order Voronoi diagram of n line segments or lines in a d-dimensional Euclidean space. The unbounded parts of these diagrams can be encoded by a Gaussian map on the sphere of directions S^(d-1). We show that the combinatorial complexity of the Gaussian map for the order-k Voronoi diagram of n line segments or lines is O(min{k,n-k} n^(d-1)), which is tight for n-k = O(1). All the d-dimensional cells of the farthest Voronoi diagram are unbounded, its (d-1)-skeleton is connected, and it does not have tunnels. A d-cell of the Voronoi diagram is called a tunnel if the set of its unbounded directions, represented as points on its Gaussian map, is not connected. In a three-dimensional space, the farthest Voronoi diagram of lines has exactly n^2-n three-dimensional cells, when n >= 2. The Gaussian map of the farthest Voronoi diagram of line segments or lines can be constructed in O(n^(d-1) alpha(n)) time, while if d=3, the time drops to worst-case optimal O(n^2).
Cite as

Gill Barequet, Evanthia Papadopoulou, and Martin Suderland. Unbounded Regions of High-Order Voronoi Diagrams of Lines and Segments in Higher Dimensions. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barequet_et_al:LIPIcs.ISAAC.2019.62,
  author =	{Barequet, Gill and Papadopoulou, Evanthia and Suderland, Martin},
  title =	{{Unbounded Regions of High-Order Voronoi Diagrams of Lines and Segments in Higher Dimensions}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.62},
  URN =		{urn:nbn:de:0030-drops-115582},
  doi =		{10.4230/LIPIcs.ISAAC.2019.62},
  annote =	{Keywords: Voronoi diagram, lines, line segments, higher-order, order-k, unbounded, hypersphere arrangement, great hyperspheres}
}
  • Refine by Author
  • 6 Suderland, Martin
  • 5 Papadopoulou, Evanthia
  • 3 Mantas, Ioannis
  • 2 Yap, Chee
  • 1 Alegría, Carlos
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 Voronoi diagram
  • 2 Fermat point
  • 2 n-ellipse
  • 1 Brocard angle
  • 1 Consistent Digital Line Segments
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2021
  • 1 2019
  • 1 2020
  • 1 2022

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