Search Results

Documents authored by Urhausen, Jérôme

Document
DOI: 10.4230/LIPIcs.MFCS.2021.56
Obstructing Classification via Projection

Authors: Pantea Haghighatkhah, Wouter Meulemans, Bettina Speckmann, Jérôme Urhausen, and Kevin Verbeek

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
Machine learning and data mining techniques are effective tools to classify large amounts of data. But they tend to preserve any inherent bias in the data, for example, with regards to gender or race. Removing such bias from data or the learned representations is quite challenging. In this paper we study a geometric problem which models a possible approach for bias removal. Our input is a set of points P in Euclidean space ℝ^d and each point is labeled with k binary-valued properties. A priori we assume that it is "easy" to classify the data according to each property. Our goal is to obstruct the classification according to one property by a suitable projection to a lower-dimensional Euclidean space ℝ^m (m < d), while classification according to all other properties remains easy. What it means for classification to be easy depends on the classification model used. We first consider classification by linear separability as employed by support vector machines. We use Kirchberger’s Theorem to show that, under certain conditions, a simple projection to ℝ^{d-1} suffices to eliminate the linear separability of one of the properties whilst maintaining the linear separability of the other properties. We also study the problem of maximizing the linear "inseparability" of the chosen property. Second, we consider more complex forms of separability and prove a connection between the number of projections required to obstruct classification and the Helly-type properties of such separabilities.
Cite as

Pantea Haghighatkhah, Wouter Meulemans, Bettina Speckmann, Jérôme Urhausen, and Kevin Verbeek. Obstructing Classification via Projection. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 56:1-56:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{haghighatkhah_et_al:LIPIcs.MFCS.2021.56,
  author =	{Haghighatkhah, Pantea and Meulemans, Wouter and Speckmann, Bettina and Urhausen, J\'{e}r\^{o}me and Verbeek, Kevin},
  title =	{{Obstructing Classification via Projection}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{56:1--56:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.56},
  URN =		{urn:nbn:de:0030-drops-144965},
  doi =		{10.4230/LIPIcs.MFCS.2021.56},
  annote =	{Keywords: Projection, classification, models of learning}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.5
Chasing Puppies: Mobile Beacon Routing on Closed Curves

Authors: Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta

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

Abstract
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others’ work on beacon-based routing. Consider a human and a puppy on a simple closed curve in the plane. The human can walk along the curve at bounded speed and change direction as desired. The puppy runs with unbounded speed along the curve as long as the Euclidean straight-line distance to the human is decreasing, so that it is always at a point on the curve where the distance is locally minimal. Assuming that the curve is smooth (with some mild genericity constraints) or a simple polygon, we prove that the human can always catch the puppy in finite time.
Cite as

Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta. Chasing Puppies: Mobile Beacon Routing on Closed Curves. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2021.5,
  author =	{Abrahamsen, Mikkel and Erickson, Jeff and Kostitsyna, Irina and L\"{o}ffler, Maarten and Miltzow, Tillmann and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi and Viglietta, Giovanni},
  title =	{{Chasing Puppies: Mobile Beacon Routing on Closed Curves}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{5:1--5:19},
  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.5},
  URN =		{urn:nbn:de:0030-drops-138046},
  doi =		{10.4230/LIPIcs.SoCG.2021.5},
  annote =	{Keywords: Beacon routing, navigation, generic smooth curves, puppies}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.71
The Spiroplot App (Media Exposition)

Authors: Casper van Dommelen, Marc van Kreveld, and Jérôme Urhausen

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

Abstract
We introduce an app for generating spiroplots, based on a new discrete-time, linear, dynamic system that repeatedly rotates a pair of points, and plots points where they land. The app supports easy definition of the initial situation and has various visualization settings. It can be accessed at https://spiroplot.sites.uu.nl.
Cite as

Casper van Dommelen, Marc van Kreveld, and Jérôme Urhausen. The Spiroplot App (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 71:1-71:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vandommelen_et_al:LIPIcs.SoCG.2020.71,
  author =	{van Dommelen, Casper and van Kreveld, Marc and Urhausen, J\'{e}r\^{o}me},
  title =	{{The Spiroplot App}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{71:1--71:5},
  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.71},
  URN =		{urn:nbn:de:0030-drops-122292},
  doi =		{10.4230/LIPIcs.SoCG.2020.71},
  annote =	{Keywords: generative art, dynamic system, pattern generation tool}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.50
The k-Fréchet Distance: How to Walk Your Dog While Teleporting

Authors: Hugo Alves Akitaya, Maike Buchin, Leonie Ryvkin, and Jérôme Urhausen

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

Abstract
We introduce a new distance measure for comparing polygonal chains: the k-Fréchet distance. As the name implies, it is closely related to the well-studied Fréchet distance but detects similarities between curves that resemble each other only piecewise. The parameter k denotes the number of subcurves into which we divide the input curves (thus we allow up to k-1 "teleports" on each input curve). The k-Fréchet distance provides a nice transition between (weak) Fréchet distance and Hausdorff distance. However, we show that deciding this distance measure turns out to be NP-hard, which is interesting since both (weak) Fréchet and Hausdorff distance are computable in polynomial time. Nevertheless, we give several possibilities to deal with the hardness of the k-Fréchet distance: besides a short exponential-time algorithm for the general case, we give a polynomial-time algorithm for k=2, i.e., we ask that we subdivide our input curves into two subcurves each. We can also approximate the optimal k by factor 2. We then present a more intricate FPT algorithm using parameters k (the number of allowed subcurves) and z (the number of segments of one curve that intersect the epsilon-neighborhood of a point on the other curve).
Cite as

Hugo Alves Akitaya, Maike Buchin, Leonie Ryvkin, and Jérôme Urhausen. The k-Fréchet Distance: How to Walk Your Dog While Teleporting. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{alvesakitaya_et_al:LIPIcs.ISAAC.2019.50,
  author =	{Alves Akitaya, Hugo and Buchin, Maike and Ryvkin, Leonie and Urhausen, J\'{e}r\^{o}me},
  title =	{{The k-Fr\'{e}chet Distance: How to Walk Your Dog While Teleporting}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{50:1--50: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.50},
  URN =		{urn:nbn:de:0030-drops-115462},
  doi =		{10.4230/LIPIcs.ISAAC.2019.50},
  annote =	{Keywords: Measures, Fr\'{e}chet distance, Hardness, FPT}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.52
Convex Partial Transversals of Planar Regions

Authors: Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma

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

Abstract
We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.
Cite as

Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma. Convex Partial Transversals of Planar Regions. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{keikha_et_al:LIPIcs.ISAAC.2018.52,
  author =	{Keikha, Vahideh and van de Kerkhof, Mees and van Kreveld, Marc and Kostitsyna, Irina and L\"{o}ffler, Maarten and Staals, Frank and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi L. and Wiratma, Lionov},
  title =	{{Convex Partial Transversals of Planar Regions}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{52:1--52:12},
  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.52},
  URN =		{urn:nbn:de:0030-drops-100003},
  doi =		{10.4230/LIPIcs.ISAAC.2018.52},
  annote =	{Keywords: computational geometry, algorithms, NP-hardness, convex transversals}
}
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