Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Free, publiclyaccessible full text available September 1, 2025

Mulzer, Wolfgang ; Phillips, Jeff M (Ed.)Let P be a set of m points in ℝ², let Σ be a set of n semialgebraic sets of constant complexity in ℝ², 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∩σ) for every σ ∈ Σ in overall expected time O^*(m^{2s/(5s4)}n^{(5s6)/(5s4)} + m^{2/3}n^{2/3} + m + n), where s > 0 is a constant that bounds the maximum complexity of the regions of Σ, and where the O^*(⋅) notation hides subpolynomial factors. For s ≥ 3, surprisingly, this bound is smaller than the bestknown bound for answering m such queries in an online manner. The latter takes O^*(m^{s/(2s1)}n^{(2s2)/(2s1)} + 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 ℬ_Φ of Σ_Φ P into bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) O^*(m^{2s/(5s4)}n^{(5s6)/(5s4)} + m^{2/3}n^{2/3} + m + n). It is straightforward to compute w(P∩σ) for all σ ∈ Σ from ℬ_Φ. Similarly, if η: Σ → S is a weight function on the regions of Σ, ∑_{σ ∈ Σ: p ∈ σ} η(σ), for every point p ∈ P, can be computed from ℬ_Φ in a straightforward manner. We also mention a few other applications of computing ℬ_Φ.more » « lessFree, publiclyaccessible full text available January 1, 2025

Let T be a set of n planar semialgebraic regions in R^3 of constant complexity (e.g., triangles, disks), which we call _plates_. We wish to preprocess T into a data structure so that for a query object gamma, which is also a plate, we can quickly answer various intersection queries, such as detecting whether gamma intersects any plate of T, reporting all the plates intersected by gamma, or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constantdegree algebraic arcs in R^3 (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in R^3. Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling the general case. By combining the polynomialpartitioning technique with additional tools from real algebraic geometry, we obtain a variety of results with different storage and querytime bounds, depending on the complexity of the input and query objects. For example, if T is a set of plates and the query objects are arcs, we obtain a data structure that uses O^*(n^(4/3)) storage (where the O^*(...) notation hides subpolynomial factors) and answers an intersection query in O^*(n^(2/3)) time. Alternatively, by increasing the storage to O^*(n^(3/2)), the query time can be decreased to O^*(n^(rho)), where rho = (2t3)/(3(t1)) < 2/3 and t≤3 is the number of parameters needed to represent the query arcs.more » « less

Ahn, HeeKap Ahn ; Sadakane, Kunihiko (Ed.)