Semi-Algebraic Off-line Range Searching and Biclique Partitions in the Plane.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 192011820 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Semi-Algebraic Off-line Range Searching and Biclique Partitions in the Plane. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Agarwal%2C+Pankaj+K%2E%22">Agarwal, Pankaj K.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> pankaj@cs.duke.edu</i><br /><searchLink fieldCode="AR" term="%22Ezra%2C+Esther%22">Ezra, Esther</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> ezraest@cs.biu.ac.il</i><br /><searchLink fieldCode="AR" term="%22Sharir%2C+Micha%22">Sharir, Micha</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> michas@tauex.tau.ac.il</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Discrete+%26+Computational+Geometry%22">Discrete & Computational Geometry</searchLink>. Mar2026, Vol. 75 Issue 2, p320-342. 23p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Semialgebraic+sets%22">Semialgebraic sets</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+geometry%22">Computational geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Predicate+%28Logic%29%22">Predicate (Logic)</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+theory%22">Graph theory</searchLink><br /><searchLink fieldCode="DE" term="%22Semigroups+%28Algebra%29%22">Semigroups (Algebra)</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=192011820 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00454-025-00792-9 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 23 StartPage: 320 Subjects: – SubjectFull: Semialgebraic sets Type: general – SubjectFull: Computational geometry Type: general – SubjectFull: Predicate (Logic) Type: general – SubjectFull: Graph theory Type: general – SubjectFull: Semigroups (Algebra) Type: general – SubjectFull: Algorithms Type: general Titles: – TitleFull: Semi-Algebraic Off-line Range Searching and Biclique Partitions in the Plane. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Agarwal, Pankaj K. – PersonEntity: Name: NameFull: Ezra, Esther – PersonEntity: Name: NameFull: Sharir, Micha IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 03 Text: Mar2026 Type: published Y: 2026 Identifiers: – Type: issn-print Value: 01795376 Numbering: – Type: volume Value: 75 – Type: issue Value: 2 Titles: – TitleFull: Discrete & Computational Geometry Type: main |
| ResultId | 1 |
