Search Results

Documents authored by Kalavas, Andreas

Document
DOI: 10.4230/LIPIcs.SoCG.2026.60
Space-Efficient Approximate Spherical Range Counting in High Dimensions

Authors: Andreas Kalavas and Ioannis Psarros

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

Abstract
We study the following range searching problem in high-dimensional Euclidean spaces: given a finite set P ⊂ ℝ^d, where each p ∈ P is assigned a weight w_p, and radius r > 0, we need to preprocess P into a data structure such that when a new query point q ∈ ℝ^d arrives, the data structure reports the cumulative weight of points of P within Euclidean distance r from q. Solving the problem exactly seems to require space usage that is exponential to the dimension, a phenomenon known as the curse of dimensionality. Thus, we focus on approximate solutions where points up to (1+ε)r away from q may be taken into account, where ε > 0 is an input parameter known during preprocessing. We build a data structure with near-linear space usage, and query time in n^{1-Θ(ε⁴/log(1/ε))}+t_q^ϱ⋅n^{1-ϱ}, for some ϱ = Θ(ε²), where t_q is the number of points of P in the ambiguity zone, i.e., at distance between r and (1+ε)r from the query q. To the best of our knowledge, this is the first data structure with efficient space usage (subquadratic or near-linear for any ε > 0) and query time that remains sublinear for any sublinear t_q. We supplement our worst-case bounds with a query-driven preprocessing algorithm to build data structures that are well-adapted to the query distribution.
Cite as

Andreas Kalavas and Ioannis Psarros. Space-Efficient Approximate Spherical Range Counting in High Dimensions. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kalavas_et_al:LIPIcs.SoCG.2026.60,
  author =	{Kalavas, Andreas and Psarros, Ioannis},
  title =	{{Space-Efficient Approximate Spherical Range Counting in High Dimensions}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{60:1--60:15},
  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.60},
  URN =		{urn:nbn:de:0030-drops-258670},
  doi =		{10.4230/LIPIcs.SoCG.2026.60},
  annote =	{Keywords: Approximate range counting, partition trees, high dimensions}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.58
A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP

Authors: Andreas Kalavas, Charalampos Platanos, and Thanos Tolias

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In Online Sorting, an array of n initially empty cells is given. At each time step t, an element x_t ∈ [0,1] arrives and must be irrevocably placed in an empty cell without knowledge of future arrivals. We aim to minimize the sum of absolute differences between pairs of elements placed in consecutive array cells, seeking an online placement strategy that results in a final array close to a sorted one. An interesting multidimensional generalization, referred to as the Online Traveling Salesperson Problem, arises when the request sequence consists of points in the d-dimensional unit cube and the objective is to minimize the sum of Euclidean distances between points in consecutive cells. Motivated by the recent work of (Abrahamsen, Bercea, Beretta, Klausen and Kozma; ESA 2024), we consider the stochastic version of Online Sorting (resp. Online TSP), where each element (resp. point) x_t is an i.i.d. sample from the uniform distribution on [0, 1] (resp. [0,1]^d). By carefully decomposing the request sequence into a hierarchy of balls-into-bins instances, where the balls to bins ratio is large enough so that bin occupancy is sharply concentrated around its mean and small enough so that we can efficiently deal with the elements placed in the same bin, we obtain an online algorithm that approximates the optimal cost within a factor of O(log² n) with high probability. Our result comprises an exponential improvement over the previously best known competitive ratio of Õ(n^{1/4}) for Stochastic Online Sorting due to (Abrahamsen et al.; ESA 2024) and O(√n) for (adversarial) Online TSP due to (Bertram, ESA 2025).
Cite as

Andreas Kalavas, Charalampos Platanos, and Thanos Tolias. A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 58:1-58:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kalavas_et_al:LIPIcs.STACS.2026.58,
  author =	{Kalavas, Andreas and Platanos, Charalampos and Tolias, Thanos},
  title =	{{A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{58:1--58:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.58},
  URN =		{urn:nbn:de:0030-drops-255473},
  doi =		{10.4230/LIPIcs.STACS.2026.58},
  annote =	{Keywords: sorting, online algorithm, balls-into-bins, TSP}
}
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