Search Results

Documents authored by Jones, Mitchell

Document
DOI: 10.4230/LIPIcs.SoCG.2021.42
Stabbing Convex Bodies with Lines and Flats

Authors: Sariel Har-Peled and Mitchell Jones

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

Abstract
We study the problem of constructing weak ε-nets where the stabbing elements are lines or k-flats instead of points. We study this problem in the simplest setting where it is still interesting - namely, the uniform measure of volume over the hypercube [0,1]^d. Specifically, a (k,ε)-net is a set of k-flats, such that any convex body in [0,1]^d of volume larger than ε is stabbed by one of these k-flats. We show that for k ≥ 1, one can construct (k,ε)-nets of size O(1/ε^{1-k/d}). We also prove that any such net must have size at least Ω(1/ε^{1-k/d}). As a concrete example, in three dimensions all ε-heavy bodies in [0,1]³ can be stabbed by Θ(1/ε^{2/3}) lines. Note, that these bounds are sublinear in 1/ε, and are thus somewhat surprising.
Cite as

Sariel Har-Peled and Mitchell Jones. Stabbing Convex Bodies with Lines and Flats. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 42:1-42:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SoCG.2021.42,
  author =	{Har-Peled, Sariel and Jones, Mitchell},
  title =	{{Stabbing Convex Bodies with Lines and Flats}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{42:1--42:12},
  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.42},
  URN =		{urn:nbn:de:0030-drops-138412},
  doi =		{10.4230/LIPIcs.SoCG.2021.42},
  annote =	{Keywords: Discrete geometry, combinatorics, weak \epsilon-nets, k-flats}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.64
Active Learning a Convex Body in Low Dimensions

Authors: Sariel Har-Peled, Mitchell Jones, and Saladi Rahul

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Consider a set P ⊆ ℝ^d of n points, and a convex body C provided via a separation oracle. The task at hand is to decide for each point of P if it is in C using the fewest number of oracle queries. We show that one can solve this problem in two and three dimensions using O(⬡_P log n) queries, where ⬡_P is the largest subset of points of P in convex position. In 2D, we provide an algorithm which efficiently generates these adaptive queries. Furthermore, we show that in two dimensions one can solve this problem using O(⊚(P,C) log² n) oracle queries, where ⊚(P,C) is a lower bound on the minimum number of queries that any algorithm for this specific instance requires. Finally, we consider other variations on the problem, such as using the fewest number of queries to decide if C contains all points of P. As an application of the above, we show that the discrete geometric median of a point set P in ℝ² can be computed in O(n log² n (log n log log n + ⬡(P))) expected time.
Cite as

Sariel Har-Peled, Mitchell Jones, and Saladi Rahul. Active Learning a Convex Body in Low Dimensions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 64:1-64:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.ICALP.2020.64,
  author =	{Har-Peled, Sariel and Jones, Mitchell and Rahul, Saladi},
  title =	{{Active Learning a Convex Body in Low Dimensions}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{64:1--64:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.64},
  URN =		{urn:nbn:de:0030-drops-124711},
  doi =		{10.4230/LIPIcs.ICALP.2020.64},
  annote =	{Keywords: Approximation algorithms, computational geometry, separation oracles, active learning}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.50
Fast Algorithms for Geometric Consensuses

Authors: Sariel Har-Peled and Mitchell Jones

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

Abstract
Let P be a set of n points in ℝ^d in general position. A median hyperplane (roughly) splits the point set P in half. The yolk of P is the ball of smallest radius intersecting all median hyperplanes of P. The egg of P is the ball of smallest radius intersecting all hyperplanes which contain exactly d points of P. We present exact algorithms for computing the yolk and the egg of a point set, both running in expected time O(n^(d-1) log n). The running time of the new algorithm is a polynomial time improvement over existing algorithms. We also present algorithms for several related problems, such as computing the Tukey and center balls of a point set, among others.
Cite as

Sariel Har-Peled and Mitchell Jones. Fast Algorithms for Geometric Consensuses. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SoCG.2020.50,
  author =	{Har-Peled, Sariel and Jones, Mitchell},
  title =	{{Fast Algorithms for Geometric Consensuses}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{50:1--50:16},
  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.50},
  URN =		{urn:nbn:de:0030-drops-122088},
  doi =		{10.4230/LIPIcs.SoCG.2020.50},
  annote =	{Keywords: Geometric optimization, centerpoint, voting games}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.41
Journey to the Center of the Point Set

Authors: Sariel Har-Peled and Mitchell Jones

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We revisit an algorithm of Clarkson et al. [K. L. Clarkson et al., 1996], that computes (roughly) a 1/(4d^2)-centerpoint in O~(d^9) time, for a point set in R^d, where O~ hides polylogarithmic terms. We present an improved algorithm that computes (roughly) a 1/d^2-centerpoint with running time O~(d^7). While the improvements are (arguably) mild, it is the first progress on this well known problem in over twenty years. The new algorithm is simpler, and the running time bound follows by a simple random walk argument, which we believe to be of independent interest. We also present several new applications of the improved centerpoint algorithm.
Cite as

Sariel Har-Peled and Mitchell Jones. Journey to the Center of the Point Set. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SoCG.2019.41,
  author =	{Har-Peled, Sariel and Jones, Mitchell},
  title =	{{Journey to the Center of the Point Set}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.41},
  URN =		{urn:nbn:de:0030-drops-104454},
  doi =		{10.4230/LIPIcs.SoCG.2019.41},
  annote =	{Keywords: Computational geometry, Centerpoints, Random walks}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.21
On Locality-Sensitive Orderings and Their Applications

Authors: Timothy M. Chan, Sariel Har-Peled, and Mitchell Jones

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
For any constant d and parameter epsilon > 0, we show the existence of (roughly) 1/epsilon^d orderings on the unit cube [0,1)^d, such that any two points p, q in [0,1)^d that are close together under the Euclidean metric are "close together" in one of these linear orderings in the following sense: the only points that could lie between p and q in the ordering are points with Euclidean distance at most epsilon | p - q | from p or q. These orderings are extensions of the Z-order, and they can be efficiently computed. Functionally, the orderings can be thought of as a replacement to quadtrees and related structures (like well-separated pair decompositions). We use such orderings to obtain surprisingly simple algorithms for a number of basic problems in low-dimensional computational geometry, including (i) dynamic approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic approximate minimum spanning trees, (iv) static and dynamic fault-tolerant spanners, and (v) approximate nearest neighbor search.
Cite as

Timothy M. Chan, Sariel Har-Peled, and Mitchell Jones. On Locality-Sensitive Orderings and Their Applications. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ITCS.2019.21,
  author =	{Chan, Timothy M. and Har-Peled, Sariel and Jones, Mitchell},
  title =	{{On Locality-Sensitive Orderings and Their Applications}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.21},
  URN =		{urn:nbn:de:0030-drops-101140},
  doi =		{10.4230/LIPIcs.ITCS.2019.21},
  annote =	{Keywords: Approximation algorithms, Data structures, Computational geometry}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.13
Turbocharging Treewidth Heuristics

Authors: Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre, and Stefan Rümmele

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
A widely used class of algorithms for computing tree decompositions of graphs are heuristics that compute an elimination order, i.e., a permutation of the vertex set. In this paper, we propose to turbocharge these heuristics. For a target treewidth k, suppose the heuristic has already computed a partial elimination order of width at most k, but extending it by one more vertex exceeds the target width k. At this moment of regret, we solve a subproblem which is to recompute the last c positions of the partial elimination order such that it can be extended without exceeding width k. We show that this subproblem is fixed-parameter tractable when parameterized by k and c, but it is para-NP-hard and W[1]-hard when parameterized by only k or c, respectively. Our experimental evaluation of the FPT algorithm shows that we can trade a reasonable increase of the running time for quality of the solution.
Cite as

Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre, and Stefan Rümmele. Turbocharging Treewidth Heuristics. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.IPEC.2016.13,
  author =	{Gaspers, Serge and Gudmundsson, Joachim and Jones, Mitchell and Mestre, Juli\'{a}n and R\"{u}mmele, Stefan},
  title =	{{Turbocharging Treewidth Heuristics}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.13},
  URN =		{urn:nbn:de:0030-drops-69322},
  doi =		{10.4230/LIPIcs.IPEC.2016.13},
  annote =	{Keywords: tree decomposition, heuristic, fixed-parameter tractability, local search}
}
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