2 Search Results for "Soberón, Pablo"

Document
DOI: 10.4230/LIPIcs.SoCG.2023.55
Combinatorial Depth Measures for Hyperplane Arrangements

Authors: Patrick Schnider and Pablo Soberón

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

Abstract
Regression depth, introduced by Rousseeuw and Hubert in 1999, is a notion that measures how good of a regression hyperplane a given query hyperplane is with respect to a set of data points. Under projective duality, this can be interpreted as a depth measure for query points with respect to an arrangement of data hyperplanes. The study of depth measures for query points with respect to a set of data points has a long history, and many such depth measures have natural counterparts in the setting of hyperplane arrangements. For example, regression depth is the counterpart of Tukey depth. Motivated by this, we study general families of depth measures for hyperplane arrangements and show that all of them must have a deep point. Along the way we prove a Tverberg-type theorem for hyperplane arrangements, giving a positive answer to a conjecture by Rousseeuw and Hubert from 1999. We also get three new proofs of the centerpoint theorem for regression depth, all of which are either stronger or more general than the original proof by Amenta, Bern, Eppstein, and Teng. Finally, we prove a version of the center transversal theorem for regression depth.
Cite as

Patrick Schnider and Pablo Soberón. Combinatorial Depth Measures for Hyperplane Arrangements. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 55:1-55:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{schnider_et_al:LIPIcs.SoCG.2023.55,
  author =	{Schnider, Patrick and Sober\'{o}n, Pablo},
  title =	{{Combinatorial Depth Measures for Hyperplane Arrangements}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{55:1--55:14},
  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.55},
  URN =		{urn:nbn:de:0030-drops-179055},
  doi =		{10.4230/LIPIcs.SoCG.2023.55},
  annote =	{Keywords: Depth measures, Hyperplane arrangements, Regression depth, Tverberg theorem}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.51
Improved Approximation Algorithms for Tverberg Partitions

Authors: Sariel Har-Peled and Timothy Zhou

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

Abstract
Tverberg’s theorem states that a set of n points in ℝ^d can be partitioned into ⌈n/(d+1)⌉ sets whose convex hulls all intersect. A point in the intersection (aka Tverberg point) is a centerpoint, or high-dimensional median, of the input point set. While randomized algorithms exist to find centerpoints with some failure probability, a partition for a Tverberg point provides a certificate of its correctness. Unfortunately, known algorithms for computing exact Tverberg points take n^{O(d²)} time. We provide several new approximation algorithms for this problem, which improve running time or approximation quality over previous work. In particular, we provide the first strongly polynomial (in both n and d) approximation algorithm for finding a Tverberg point.
Cite as

Sariel Har-Peled and Timothy Zhou. Improved Approximation Algorithms for Tverberg Partitions. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 51:1-51:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.ESA.2021.51,
  author =	{Har-Peled, Sariel and Zhou, Timothy},
  title =	{{Improved Approximation Algorithms for Tverberg Partitions}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{51:1--51:15},
  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.51},
  URN =		{urn:nbn:de:0030-drops-146323},
  doi =		{10.4230/LIPIcs.ESA.2021.51},
  annote =	{Keywords: Geometric spanners, vertex failures, robustness}
}
  • Refine by Author
  • 1 Har-Peled, Sariel
  • 1 Schnider, Patrick
  • 1 Soberón, Pablo
  • 1 Zhou, Timothy

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Combinatorics

  • Refine by Keyword
  • 1 Depth measures
  • 1 Geometric spanners
  • 1 Hyperplane arrangements
  • 1 Regression depth
  • 1 Tverberg theorem
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact