View in EDS

Semi-Algebraic Off-line Range Searching and Biclique Partitions in the Plane.

Saved in:
Bibliographic Details
Title: Semi-Algebraic Off-line Range Searching and Biclique Partitions in the Plane.
Authors: Agarwal, Pankaj K.1 (AUTHOR) pankaj@cs.duke.edu, Ezra, Esther2 (AUTHOR) ezraest@cs.biu.ac.il, Sharir, Micha3 (AUTHOR) michas@tauex.tau.ac.il
Source: Discrete & Computational Geometry. Mar2026, Vol. 75 Issue 2, p320-342. 23p.
Subjects: Semialgebraic sets, Computational geometry, Predicate (Logic), Graph theory, Semigroups (Algebra), Algorithms
Abstract: Let P be a set of m points in R 2 , let Σ be a set of n semi-algebraic sets of constant complexity in R 2 , let (S , +) be a semigroup, and let w : P → S be a weight function on the points of P. We describe a randomized algorithm for computing w (P ∩ σ) = ∑ p ∈ P ∩ σ w (p) for every σ ∈ Σ in overall expected time O ∗ (m 2 s 5 s - 4 n 5 s - 6 5 s - 4 + m 2 / 3 n 2 / 3 + m + n) , where s > 0 is the number of degrees of freedom of the regions of Σ , and where the O ∗ (·) notation hides subpolynomial factors. For s ≥ 3 , surprisingly, this bound is smaller than the best-known bound for answering m such queries in an on-line manner; the latter takes O ∗ (m s 2 s - 1 n 2 s - 2 2 s - 1 + m + n) time. Let Φ : Σ × P → { 0 , 1 } be the Boolean predicate (of constant complexity) such that Φ (σ , p) = 1 if p ∈ σ and 0 otherwise, and let Σ Φ P = { (σ , p) ∈ Σ × P ∣ Φ (σ , p) = 1 } . Our algorithm actually computes a partition B Φ of Σ Φ P into (edge-disjoint) bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) O ∗ (m 2 s 5 s - 4 n 5 s - 6 5 s - 4 + m 2 / 3 n 2 / 3 + m + n) . It is straightforward to compute w (P ∩ σ) for all σ ∈ Σ from B Φ . Similarly, if η : Σ → S is a weight function on the regions of Σ , ∑ σ ∈ Σ : p ∈ σ η (σ) , for every point p ∈ P , can be computed from B Φ in a straightforward manner, in the same asymptotic time bound. A recent work of Chan et al. [28] solves the on-line version of this dual point enclosure problem within the same performance bound as our off-line solution. [ABSTRACT FROM AUTHOR]
Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:Let P be a set of m points in R 2 , let Σ be a set of n semi-algebraic sets of constant complexity in R 2 , let (S , +) be a semigroup, and let w : P → S be a weight function on the points of P. We describe a randomized algorithm for computing w (P ∩ σ) = ∑ p ∈ P ∩ σ w (p) for every σ ∈ Σ in overall expected time O ∗ (m 2 s 5 s - 4 n 5 s - 6 5 s - 4 + m 2 / 3 n 2 / 3 + m + n) , where s > 0 is the number of degrees of freedom of the regions of Σ , and where the O ∗ (·) notation hides subpolynomial factors. For s ≥ 3 , surprisingly, this bound is smaller than the best-known bound for answering m such queries in an on-line manner; the latter takes O ∗ (m s 2 s - 1 n 2 s - 2 2 s - 1 + m + n) time. Let Φ : Σ × P → { 0 , 1 } be the Boolean predicate (of constant complexity) such that Φ (σ , p) = 1 if p ∈ σ and 0 otherwise, and let Σ Φ P = { (σ , p) ∈ Σ × P ∣ Φ (σ , p) = 1 } . Our algorithm actually computes a partition B Φ of Σ Φ P into (edge-disjoint) bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) O ∗ (m 2 s 5 s - 4 n 5 s - 6 5 s - 4 + m 2 / 3 n 2 / 3 + m + n) . It is straightforward to compute w (P ∩ σ) for all σ ∈ Σ from B Φ . Similarly, if η : Σ → S is a weight function on the regions of Σ , ∑ σ ∈ Σ : p ∈ σ η (σ) , for every point p ∈ P , can be computed from B Φ in a straightforward manner, in the same asymptotic time bound. A recent work of Chan et al. [28] solves the on-line version of this dual point enclosure problem within the same performance bound as our off-line solution. [ABSTRACT FROM AUTHOR]
ISSN:01795376
DOI:10.1007/s00454-025-00792-9