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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let U be a set of n possibly intersecting (d1)-simplices in &space for d _> 2, and let 4(V) be the arrangement of V. Let K 14(U)I be the number of faces of any dimension in the arrangement of U. A data structure is described that uses storage O(nd-l+e K) and is built deterministically in time O(nd-l+e + Klogn), where > 0 is an arbitrarily small constant, such that the face of 4(U) containing a query point is located in time O(loga n). If two query points are in the same cell of 4(U), a collision-free path connecting them is produced. This result is obtained by exploiting powerful and so far overlooked properties of sparse nets introduced by Chazelle [Discrete Cornput. Geom., 9 (1993), pp. 145-158]. If the (d1)-simplices in V have pairwise-disjoint interiors and d >_ 3, improved bounds are obtained. A data structure is described that uses O(nd-l) storage and is built deterministically in time O(nd-l) such that point-location queries are solved in time O(logn). Also, as a by-product, this method gives the first optimal worst-case algorithm for triangulating a nonsimple polyhedron in 3-space. Key words, arrangements of simplices, point location, sparse nets, motion planning, triangulations AMS subject classifications. 68P05, 68Q25, 68Q40, 68U05

On point location and motion planning among simplices