2 Search Results for "Niemeier, Martin"

Document

DOI: 10.4230/LIPIcs.WADS.2025.48

Farthest-Point Voronoi Diagrams in the Hilbert Metric

Authors: Minju Song, Mook Kwon Jung, and Hee-Kap Ahn

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

The Hilbert metric, introduced by David Hilbert in 1895, is a projective metric defined on a bounded convex domain in a Euclidean space. For a convex polygon with m vertices and n point sites lying inside the polygon in the plane, it is shown that the nearest-point Voronoi diagram in the Hilbert metric has combinatorial complexity of O(mn) [Gezalyan and Mount, SoCG 2023]. In this paper, we show that the farthest-point Voronoi diagram in the Hilbert metric has combinatorial complexity O(m), which is independent of the number of sites. Also, we present an efficient algorithm to compute the farthest-point Voronoi diagram.

Cite as

Minju Song, Mook Kwon Jung, and Hee-Kap Ahn. Farthest-Point Voronoi Diagrams in the Hilbert Metric. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{song_et_al:LIPIcs.WADS.2025.48,
  author =	{Song, Minju and Jung, Mook Kwon and Ahn, Hee-Kap},
  title =	{{Farthest-Point Voronoi Diagrams in the Hilbert Metric}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.48},
  URN =		{urn:nbn:de:0030-drops-242797},
  doi =		{10.4230/LIPIcs.WADS.2025.48},
  annote =	{Keywords: Farthest-point Voronoi diagram, Hilbert metric, Complexity, Algorithm}
}

Document

DOI: 10.4230/DagSemProc.10071.13

Scheduling periodic tasks in a hard real-time environment

Authors: Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, Jose Verschae, and Andreas Wiese

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract

We consider a real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks $ au_i=(c_i,p_i)$ on a minimum number of identical machines and to compute offsets $a_i$ for the tasks such that no collision occurs. A task $ au_i$ releases a job of running time $c_i$ at each time $a_i + kcdot p_i, , k in mathbb{N}_0$ and a collision occurs if two jobs are simultaneously active on the same machine. We shed some light on the complexity and approximability landscape of this problem. Although the problem cannot be approximated within a factor of $n^{1-varepsilon}$ for any $varepsilon>0$, an interesting restriction is much more tractable: If the periods are dividing (for each $i,j$ one has $p_i | p_j$ or $p_j | p_i$), the problem allows for a better structured representation of solutions, which leads to a 2-approximation. This result is tight, even asymptotically.

Cite as

Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, Jose Verschae, and Andreas Wiese. Scheduling periodic tasks in a hard real-time environment. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{eisenbrand_et_al:DagSemProc.10071.13,
  author =	{Eisenbrand, Friedrich and H\"{a}hnle, Nicolai and Niemeier, Martin and Skutella, Martin and Verschae, Jose and Wiese, Andreas},
  title =	{{Scheduling periodic tasks in a hard real-time environment}},
  booktitle =	{Scheduling},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.13},
  URN =		{urn:nbn:de:0030-drops-25348},
  doi =		{10.4230/DagSemProc.10071.13},
  annote =	{Keywords: Real-Time Scheduling, Periodic scheduling problem, Periodic maintenance problem, Approximation hardness, Approximation algorithm}
}

Refine by Type
2 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2025
1 2010

Refine by Author
1 Ahn, Hee-Kap
1 Eisenbrand, Friedrich
1 Hähnle, Nicolai
1 Jung, Mook Kwon
1 Niemeier, Martin
Show More...

Refine by Series/Journal
1 LIPIcs
1 DagSemProc

Refine by Classification
1 Theory of computation → Computational geometry

Refine by Keyword
1 Algorithm
1 Approximation algorithm
1 Approximation hardness
1 Complexity
1 Farthest-point Voronoi diagram
Show More...

2 Search Results for "Niemeier, Martin"

Farthest-Point Voronoi Diagrams in the Hilbert Metric

Abstract

Cite as

Scheduling periodic tasks in a hard real-time environment

Abstract

Cite as

Thanks for your feedback!

Could not send message