English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We revisit the classic problem of simplex range searching and relatedproblems in computational geometry. We present a collection of new resultswhich improve previous bounds by multiple logarithmic factors that were causedby the use of multi-level data structures. Highlights include the following:  $\bullet$ For a set of $n$ points in a constant dimension $d$, we give datastructures with $O(n^d)$ (or slightly better) space that can answer simplexrange counting queries in optimal $O(\log n)$ time and simplex range reportingqueries in optimal $O(\log n + k)$ time, where $k$ denotes the output size. Forsemigroup range searching, we obtain $O(\log n)$ query time with$O(n^d\mathop{\rm polylog}n)$ space. Previous data structures with similarspace bounds by Matou\v{s}ek from nearly three decades ago had $O(\log^{d+1}n)$or $O(\log^{d+1}n + k)$ query time.  $\bullet$ For a set of $n$ simplices in a constant dimension $d$, we givedata structures with $O(n)$ space that can answer stabbing counting queries(counting the number of simplices containing a query point) in $O(n^{1-1/d})$time, and stabbing reporting queries in $O(n^{1-1/d}+k)$ time. Previous datastructures had extra $\log^d n$ factors in space and query time.  $\bullet$ For a set of $n$ (possibly intersecting) line segments in 2D, wegive a data structure with $O(n)$ space that can answer ray shooting queries in$O(\sqrt{n})$ time. This improves Wang's recent data structure [SoCG'20] with$O(n\log n)$ space and $O(\sqrt{n}\log n)$ query time.

Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures