8 Search Results for "He, Qizheng"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.34
On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k

Authors: Timothy M. Chan, Qizheng He, and Yuancheng Yu

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We study the time complexity of the discrete k-center problem and related (exact) geometric set cover problems when k or the size of the cover is small. We obtain a plethora of new results: - We give the first subquadratic algorithm for rectilinear discrete 3-center in 2D, running in Õ(n^{3/2}) time. - We prove a lower bound of Ω(n^{4/3-δ}) for rectilinear discrete 3-center in 4D, for any constant δ > 0, under a standard hypothesis about triangle detection in sparse graphs. - Given n points and n weighted axis-aligned unit squares in 2D, we give the first subquadratic algorithm for finding a minimum-weight cover of the points by 3 unit squares, running in Õ(n^{8/5}) time. We also prove a lower bound of Ω(n^{3/2-δ}) for the same problem in 2D, under the well-known APSP Hypothesis. For arbitrary axis-aligned rectangles in 2D, our upper bound is Õ(n^{7/4}). - We prove a lower bound of Ω(n^{2-δ}) for Euclidean discrete 2-center in 13D, under the Hyperclique Hypothesis. This lower bound nearly matches the straightforward upper bound of Õ(n^ω), if the matrix multiplication exponent ω is equal to 2. - We similarly prove an Ω(n^{k-δ}) lower bound for Euclidean discrete k-center in O(k) dimensions for any constant k ≥ 3, under the Hyperclique Hypothesis. This lower bound again nearly matches known upper bounds if ω = 2. - We also prove an Ω(n^{2-δ}) lower bound for the problem of finding 2 boxes to cover the largest number of points, given n points and n boxes in 12D . This matches the straightforward near-quadratic upper bound.
Cite as

Timothy M. Chan, Qizheng He, and Yuancheng Yu. On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ICALP.2023.34,
  author =	{Chan, Timothy M. and He, Qizheng and Yu, Yuancheng},
  title =	{{On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{34:1--34:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.34},
  URN =		{urn:nbn:de:0030-drops-180868},
  doi =		{10.4230/LIPIcs.ICALP.2023.34},
  annote =	{Keywords: Geometric set cover, discrete k-center, conditional lower bounds}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.11
Minimum-Membership Geometric Set Cover, Revisited

Authors: Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue

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

Abstract
We revisit a natural variant of the geometric set cover problem, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set S of points and a set ℛ of geometric objects, and the goal is to find a subset ℛ^* ⊆ ℛ to cover all points in S such that the membership of S with respect to ℛ^*, denoted by memb(S,ℛ^*), is minimized, where memb(S,ℛ^*) = max_{p ∈ S} |{R ∈ ℛ^*: p ∈ R}|. We give the first polynomial-time approximation algorithms for MMGSC in ℝ². Specifically, we achieve the following two main results. - We give the first polynomial-time constant-approximation algorithm for MMGSC with unit squares. This answers a question left open since the work of Erlebach and Leeuwen [SODA'08], who gave a constant-approximation algorithm with running time n^{O(opt)} where opt is the optimum of the problem (i.e., the minimum membership). - We give the first polynomial-time approximation scheme (PTAS) for MMGSC with halfplanes. Prior to this work, it was even unknown whether the problem can be approximated with a factor of o(log n) in polynomial time, while it is well-known that the minimum-size set cover problem with halfplanes can be solved in polynomial time. We also consider a problem closely related to MMGSC, called minimum-ply geometric set cover (MPGSC), in which the goal is to find ℛ^* ⊆ ℛ to cover S such that the ply of ℛ^* is minimized, where the ply is defined as the maximum number of objects in ℛ^* which have a nonempty common intersection. Very recently, Durocher et al. gave the first constant-approximation algorithm for MPGSC with unit squares which runs in O(n^{12}) time. We give a significantly simpler constant-approximation algorithm with near-linear running time.
Cite as

Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue. Minimum-Membership Geometric Set Cover, Revisited. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.11,
  author =	{Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket and Xue, Jie},
  title =	{{Minimum-Membership Geometric Set Cover, Revisited}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{11:1--11: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.11},
  URN =		{urn:nbn:de:0030-drops-178610},
  doi =		{10.4230/LIPIcs.SoCG.2023.11},
  annote =	{Keywords: geometric set cover, geometric optimization, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.25
Worst-Case Efficient Dynamic Geometric Independent Set

Authors: Jean Cardinal, John Iacono, and Grigorios Koumoutsos

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

Abstract
We consider the problem of maintaining an approximate maximum independent set of geometric objects under insertions and deletions. We present a data structure that maintains a constant-factor approximate maximum independent set for broad classes of fat objects in d dimensions, where d is assumed to be a constant, in sublinear worst-case update time. This gives the first results for dynamic independent set in a wide variety of geometric settings, such as disks, fat polygons, and their high-dimensional equivalents. For axis-aligned squares and hypercubes, our result improves upon all (recently announced) previous works. We obtain, in particular, a dynamic (4+ε)-approximation for squares, with O(log⁴ n) worst-case update time. Our result is obtained via a two-level approach. First, we develop a dynamic data structure which stores all objects and provides an approximate independent set when queried, with output-sensitive running time. We show that via standard methods such a structure can be used to obtain a dynamic algorithm with amortized update time bounds. Then, to obtain worst-case update time algorithms, we develop a generic deamortization scheme that with each insertion/deletion keeps (i) the update time bounded and (ii) the number of changes in the independent set constant. We show that such a scheme is applicable to fat objects by showing an appropriate generalization of a separator theorem. Interestingly, we show that our deamortization scheme is also necessary in order to obtain worst-case update bounds: If for a class of objects our scheme is not applicable, then no constant-factor approximation with sublinear worst-case update time is possible. We show that such a lower bound applies even for seemingly simple classes of geometric objects including axis-aligned rectangles in the plane.
Cite as

Jean Cardinal, John Iacono, and Grigorios Koumoutsos. Worst-Case Efficient Dynamic Geometric Independent Set. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2021.25,
  author =	{Cardinal, Jean and Iacono, John and Koumoutsos, Grigorios},
  title =	{{Worst-Case Efficient Dynamic Geometric Independent Set}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{25:1--25: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.25},
  URN =		{urn:nbn:de:0030-drops-146061},
  doi =		{10.4230/LIPIcs.ESA.2021.25},
  annote =	{Keywords: Maximum independent set, deamortization, approximation}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.SoCG.2021.2
3SUM and Related Problems in Fine-Grained Complexity (Invited Talk)

Authors: Virginia Vassilevska Williams

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

Abstract
3SUM is a simple to state problem: given a set S of n numbers, determine whether S contains three a,b,c so that a+b+c = 0. The fastest algorithms for the problem run in n² poly(log log n)/(log n)² time both when the input numbers are integers [Ilya Baran et al., 2005] (in the word RAM model with O(log n) bit words) and when they are real numbers [Timothy M. Chan, 2020] (in the real RAM model). A hypothesis that is now central in Fine-Grained Complexity (FGC) states that 3SUM requires n^{2-o(1)} time (on the real RAM for real inputs and on the word RAM with O(log n) bit numbers for integer inputs). This hypothesis was first used in Computational Geometry by Gajentaan and Overmars [A. Gajentaan and M. Overmars, 1995] who built a web of reductions showing that many geometric problems are hard, assuming that 3SUM is hard. The web of reductions within computational geometry has grown considerably since then (see some citations in [V. Vassilevska Williams, 2018]). A seminal paper by Pǎtraşcu [Mihai Pǎtraşcu, 2010] showed that the integer version of the 3SUM hypothesis can be used to prove polynomial conditional lower bounds for several problems in data structures and graph algorithms as well, extending the implications of the hypothesis to outside computational geometry. Pǎtraşcu proved an important tight equivalence between (integer) 3SUM and a problem called 3SUM-Convolution (see also [Timothy M. Chan and Qizheng He, 2020]) that is easier to use in reductions: given an integer array a of length n, do there exist i,j ∈ [n] so that a[i]+a[j] = a[i+j]. From 3SUM-Convolution, many 3SUM-based hardness results have been proven: e.g. to listing graphs in triangles, dynamically maintaining shortest paths or bipartite matching, subset intersection and many more. It is interesting to consider more runtime-equivalent formulations of 3SUM, with the goal of uncovering more relationships to different problems. The talk will outline some such equivalences. For instance, 3SUM (over the reals or the integers) is equivalent to All-Numbers-3SUM: given a set S of n numbers, determine for every a ∈ S whether there are b,c ∈ S with a+b+c = 0 (e.g. [V. Vassilevska Williams and R. Williams, 2018]). The equivalences between 3SUM, 3SUM-Convolution and All-Numbers 3SUM are (n²,n²)-fine-grained equivalences that imply that if there is an O(n^{2-ε}) time algorithm for one of the problems for ε > 0, then there is also an O(n^{2-ε'}) time algorithm for the other problems for some ε' > 0. More generally, for functions a(n),b(n), there is an (a,b)-fine-grained reduction [V. Vassilevska Williams, 2018; V. Vassilevska Williams and R. Williams, 2010; V. Vassilevska Williams and R. Williams, 2018] from problem A to problem B if for every ε > 0 there is a δ > 0 and an O(a(n)^{1-δ}) time algorithm for A that does oracle calls to instances of B of sizes n₁,…,n_k (for some k) so that ∑_{j = 1}^k b(n_j)^{1-ε} ≤ a(n)^{1-δ}. With such a reduction, an O(b(n)^{1-ε}) time algorithm for B can be converted into an O(a(n)^{1-δ}) time algorithm for A by replacing the oracle calls by calls to the B algorithm. A and B are (a,b)-fine-grained equivalent if A (a,b)-reduces to B and B (b,a)-reduces to A. One of the main open problems in FGC is to determine the relationship between 3SUM and the other central FGC problems, in particular All-Pairs Shortest Paths (APSP). A classical graph problem, APSP in n node graphs has been known to be solvable in O(n³) time since the 1950s. Its fastest known algorithm runs in n³/exp(√{log n}) time [Ryan Williams, 2014]. The APSP Hypothesis states that n^{3-o(1)} time is needed to solve APSP in graphs with integer edge weights in the word-RAM model with O(log n) bit words. It is unknown whether APSP and 3SUM are fine-grained reducible to each other, in either direction. The two problems are very similar. Problems such as (min,+)-convolution (believed to require n^{2-o(1)} time) have tight fine-grained reductions to both APSP and 3SUM, and both 3SUM and APSP have tight fine-grained reductions to problems such as Exact Triangle [V. Vassilevska Williams and R. Williams, 2018; V. Vassilevska and R. Williams, 2009; V. Vassilevska Williams and Ryan Williams, 2013] and (since very recently) Listing triangles in sparse graphs [Mihai Pǎtraşcu, 2010; Tsvi Kopelowitz et al., 2016; V. Vassilevska Williams and Yinzhan Xu, 2020]. The talk will discuss these relationships and some of their implications, e.g. to dynamic algorithms.
Cite as

Virginia Vassilevska Williams. 3SUM and Related Problems in Fine-Grained Complexity (Invited Talk). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{vassilevskawilliams:LIPIcs.SoCG.2021.2,
  author =	{Vassilevska Williams, Virginia},
  title =	{{3SUM and Related Problems in Fine-Grained Complexity}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{2:1--2:2},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.2},
  URN =		{urn:nbn:de:0030-drops-138014},
  doi =		{10.4230/LIPIcs.SoCG.2021.2},
  annote =	{Keywords: fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.25
More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time

Authors: Timothy M. Chan and Qizheng He

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

Abstract
We study geometric set cover problems in dynamic settings, allowing insertions and deletions of points and objects. We present the first dynamic data structure that can maintain an O(1)-approximation in sublinear update time for set cover for axis-aligned squares in 2D . More precisely, we obtain randomized update time O(n^{2/3+δ}) for an arbitrarily small constant δ > 0. Previously, a dynamic geometric set cover data structure with sublinear update time was known only for unit squares by Agarwal, Chang, Suri, Xiao, and Xue [SoCG 2020]. If only an approximate size of the solution is needed, then we can also obtain sublinear amortized update time for disks in 2D and halfspaces in 3D . As a byproduct, our techniques for dynamic set cover also yield an optimal randomized O(nlog n)-time algorithm for static set cover for 2D disks and 3D halfspaces, improving our earlier O(nlog n(log log n)^{O(1)}) result [SoCG 2020].
Cite as

Timothy M. Chan and Qizheng He. More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2021.25,
  author =	{Chan, Timothy M. and He, Qizheng},
  title =	{{More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{25:1--25:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.25},
  URN =		{urn:nbn:de:0030-drops-138244},
  doi =		{10.4230/LIPIcs.SoCG.2021.25},
  annote =	{Keywords: Geometric set cover, approximation algorithms, dynamic data structures, sublinear algorithms, random sampling}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.29
More on Change-Making and Related Problems

Authors: Timothy M. Chan and Qizheng He

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Given a set of n integer-valued coin types and a target value t, the well-known change-making problem asks for the minimum number of coins that sum to t, assuming an unlimited number of coins in each type. In the more general all-targets version of the problem, we want the minimum number of coins summing to j, for every j = 0,…,t. For example, the textbook dynamic programming algorithms can solve the all-targets problem in O(nt) time. Recently, Chan and He (SOSA'20) described a number of O(t polylog t)-time algorithms for the original (single-target) version of the change-making problem, but not the all-targets version. In this paper, we obtain a number of new results on change-making and related problems: - We present a new algorithm for the all-targets change-making problem with running time Õ(t^{4/3}), improving a previous Õ(t^{3/2})-time algorithm. - We present a very simple Õ(u²+t)-time algorithm for the all-targets change-making problem, where u denotes the maximum coin value. The analysis of the algorithm uses a theorem of Erdős and Graham (1972) on the Frobenius problem. This algorithm can be extended to solve the all-capacities version of the unbounded knapsack problem (for integer item weights bounded by u). - For the original (single-target) coin changing problem, we describe a simple modification of one of Chan and He’s algorithms that runs in Õ(u) time (instead of Õ(t)). - For the original (single-capacity) unbounded knapsack problem, we describe a simple algorithm that runs in Õ(nu) time, improving previous near-u²-time algorithms. - We also observe how one of our ideas implies a new result on the minimum word break problem, an optimization version of a string problem studied by Bringmann et al. (FOCS'17), generalizing change-making (which corresponds to the unary special case).
Cite as

Timothy M. Chan and Qizheng He. More on Change-Making and Related Problems. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ESA.2020.29,
  author =	{Chan, Timothy M. and He, Qizheng},
  title =	{{More on Change-Making and Related Problems}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{29:1--29:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.29},
  URN =		{urn:nbn:de:0030-drops-128958},
  doi =		{10.4230/LIPIcs.ESA.2020.29},
  annote =	{Keywords: Coin changing, knapsack, dynamic programming, Frobenius problem, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.27
Faster Approximation Algorithms for Geometric Set Cover

Authors: Timothy M. Chan and Qizheng He

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

Abstract
We improve the running times of O(1)-approximation algorithms for the set cover problem in geometric settings, specifically, covering points by disks in the plane, or covering points by halfspaces in three dimensions. In the unweighted case, Agarwal and Pan [SoCG 2014] gave a randomized O(n log⁴n)-time, O(1)-approximation algorithm, by using variants of the multiplicative weight update (MWU) method combined with geometric data structures. We simplify the data structure requirement in one of their methods and obtain a deterministic O(n log³n log log n)-time algorithm. With further new ideas, we obtain a still faster randomized O(n log n(log log n)^O(1))-time algorithm. For the weighted problem, we also give a randomized O(n log⁴n log log n)-time, O(1)-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.
Cite as

Timothy M. Chan and Qizheng He. Faster Approximation Algorithms for Geometric Set Cover. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2020.27,
  author =	{Chan, Timothy M. and He, Qizheng},
  title =	{{Faster Approximation Algorithms for Geometric Set Cover}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{27:1--27:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.27},
  URN =		{urn:nbn:de:0030-drops-121856},
  doi =		{10.4230/LIPIcs.SoCG.2020.27},
  annote =	{Keywords: Set cover, approximation algorithms, multiplicate weight update method, random sampling, shallow cuttings}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.28
Further Results on Colored Range Searching

Authors: Timothy M. Chan, Qizheng He, and Yakov Nekrich

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

Abstract
We present a number of new results about range searching for colored (or "categorical") data: 1) For a set of n colored points in three dimensions, we describe randomized data structures with O(n polylog n) space that can report the distinct colors in any query orthogonal range (axis-aligned box) in O(k polyloglog n) expected time, where k is the number of distinct colors in the range, assuming that coordinates are in {1,…,n}. Previous data structures require O((log n)/(log log n) + k) query time. Our result also implies improvements in higher constant dimensions. 2) Our data structures can be adapted to halfspace ranges in three dimensions (or circular ranges in two dimensions), achieving O(k log n) expected query time. Previous data structures require O(k log²n) query time. 3) For a set of n colored points in two dimensions, we describe a data structure with O(n polylog n) space that can answer colored "type-2" range counting queries: report the number of occurrences of every distinct color in a query orthogonal range. The query time is O((log n)/(log log n) + k log log n), where k is the number of distinct colors in the range. Naively performing k uncolored range counting queries would require O(k (log n)/(log log n)) time. Our data structures are designed using a variety of techniques, including colored variants of randomized incremental construction (which may be of independent interest), colored variants of shallow cuttings, and bit-packing tricks.
Cite as

Timothy M. Chan, Qizheng He, and Yakov Nekrich. Further Results on Colored Range Searching. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2020.28,
  author =	{Chan, Timothy M. and He, Qizheng and Nekrich, Yakov},
  title =	{{Further Results on Colored Range Searching}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{28:1--28:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.28},
  URN =		{urn:nbn:de:0030-drops-121868},
  doi =		{10.4230/LIPIcs.SoCG.2020.28},
  annote =	{Keywords: Range searching, geometric data structures, randomized incremental construction, random sampling, word RAM}
}
  • Refine by Author
  • 5 Chan, Timothy M.
  • 5 He, Qizheng
  • 1 Bandyapadhyay, Sayan
  • 1 Cardinal, Jean
  • 1 Iacono, John
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Computational geometry
  • 3 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Data structures design and analysis
  • 1 Theory of computation
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 3 approximation algorithms
  • 3 random sampling
  • 2 Geometric set cover
  • 2 fine-grained complexity
  • 1 Coin changing
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 3 2020
  • 3 2021
  • 2 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact