Search Results

Documents authored by Munteanu, Alexander

Document
DOI: 10.4230/LIPIcs.ESA.2026.116
Dimension Reduction for Curves: Simplified and Generalized

Authors: Matthijs Ebbens, Jie Lu, and Alexander Munteanu

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
We revisit random projections for reducing the dimension of high-dimensional polygonal curves. Drawing from the toolbox of randomized linear algebra, we give a considerably simplified proof of the known O(ε^{-2} log(nm)) bound on the target dimension of a random projection that preserves the continuous Fréchet distance of polygonal curves up to a factor (1±ε). Our proof is based on the concept of sparse oblivious subspace embeddings. While previous techniques were limited to the case of the Fréchet distance, our techniques are fairly general and extend to all possible distance measures that involve the maximum, a sum or an integral over Euclidean distances between pairs of points on both input curves. We define a generalized dissimilarity measure for curves that includes several popular measures such as Fréchet, q-DTW, Hausdorff, etc. as special cases and show that the same dimension reduction technique works for this generalized dissimilarity measure. Finally, we apply the same framework for dimension reduction to piecewise linear surfaces, after extending the distance measure suitably to such surfaces.
Cite as

Matthijs Ebbens, Jie Lu, and Alexander Munteanu. Dimension Reduction for Curves: Simplified and Generalized. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 116:1-116:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ebbens_et_al:LIPIcs.ESA.2026.116,
  author =	{Ebbens, Matthijs and Lu, Jie and Munteanu, Alexander},
  title =	{{Dimension Reduction for Curves: Simplified and Generalized}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{116:1--116:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.116},
  URN =		{urn:nbn:de:0030-drops-272521},
  doi =		{10.4230/LIPIcs.ESA.2026.116},
  annote =	{Keywords: dimension reduction, Fr\'{e}chet distance, dynamic time warping, polygonal curves, piecewise linear surfaces}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.80
Hardness of High-Dimensional Linear Classification

Authors: Alexander Munteanu, Simon Omlor, and Jeff M. Phillips

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem, which models linear classification. Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms. However, only O(n^d) and respectively Õ(1/ε^d) upper bounds are known and complemented by polynomial lower bounds that do not support the exponential in dimension dependence. We close this gap up to polylogarithmic terms by reduction from widely-believed hardness conjectures for Affine Degeneracy testing and k-Sum problems. Our reductions yield matching lower bounds of Ω̃(n^d) and respectively Ω̃(1/ε^d) based on Affine Degeneracy testing, and Ω̃(n^{d/2}) and respectively Ω̃(1/ε^{d/2}) conditioned on k-Sum. The first bound also holds unconditionally if the computational model is restricted to make sidedness queries, which corresponds to a widely spread setting implemented and optimized in many contemporary algorithms and computing paradigms.
Cite as

Alexander Munteanu, Simon Omlor, and Jeff M. Phillips. Hardness of High-Dimensional Linear Classification. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 80:1-80:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{munteanu_et_al:LIPIcs.SoCG.2026.80,
  author =	{Munteanu, Alexander and Omlor, Simon and Phillips, Jeff M.},
  title =	{{Hardness of High-Dimensional Linear Classification}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{80:1--80:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.80},
  URN =		{urn:nbn:de:0030-drops-258871},
  doi =		{10.4230/LIPIcs.SoCG.2026.80},
  annote =	{Keywords: Conditional Hardness, k-Sum, Affine Degeneracy, Halfspace Discrepancy, Classification}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.47
Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling

Authors: Amer Krivošija and Alexander Munteanu

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

Abstract
We study a variant of the median problem for a collection of point sets in high dimensions. This generalizes the geometric median as well as the (probabilistic) smallest enclosing ball (pSEB) problems. Our main objective and motivation is to improve the previously best algorithm for the pSEB problem by reducing its exponential dependence on the dimension to linear. This is achieved via a novel combination of sampling techniques for clustering problems in metric spaces with the framework of stochastic subgradient descent. As a result, the algorithm becomes applicable to shape fitting problems in Hilbert spaces of unbounded dimension via kernel functions. We present an exemplary application by extending the support vector data description (SVDD) shape fitting method to the probabilistic case. This is done by simulating the pSEB algorithm implicitly in the feature space induced by the kernel function.
Cite as

Amer Krivošija and Alexander Munteanu. Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{krivosija_et_al:LIPIcs.SoCG.2019.47,
  author =	{Krivo\v{s}ija, Amer and Munteanu, Alexander},
  title =	{{Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{47:1--47: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.47},
  URN =		{urn:nbn:de:0030-drops-104515},
  doi =		{10.4230/LIPIcs.SoCG.2019.47},
  annote =	{Keywords: geometric median, convex optimization, smallest enclosing ball, probabilistic data, support vector data description, kernel methods}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact