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 Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

In this paper we consider the following problem: Given a set @@@@ of <italic>n</italic> (possibly intersecting) line segments in the plane, preprocess them so that, given a query ray <italic>&rgr;</italic> emanating from a point <italic>p</italic>, we can quickly compute the intersection point &PHgr;(@@@@, <italic>&rgr;</italic>) of <italic>&rgr;</italic> with a segment of @@@@ that lies nearest to <italic>p</italic>. We present an algorithm that preprocesses @@@@, in time <italic>&Ogr;</italic>(<italic>n</italic><supscrpt>3/2</supscrpt> log<supscrpt>ω</supscrpt> <italic>n</italic>), into a data structure of size <italic>&Ogr;</italic>(<italic>n</italic>α(<italic>n</italic>) log<supscrpt>4</supscrpt> <italic>n</italic>), so that for a query ray <italic>&rgr;</italic>, &PHgr;(@@@@, <italic>&rgr;</italic>) can be computed in <italic>&Ogr;</italic>(√<italic>n</italic>log<supscrpt>3</supscrpt> <italic>n</italic>), where ω is a constant < 4.3 and α(<italic>n</italic>) is a functional inverse of Ackermann's function. If the given segments are non-intersecting, the storage goes down to <italic>&Ogr;</italic>(<italic>n</italic>log<supscrpt>3</supscrpt> <italic>n</italic>) and the query time is only <italic>&Ogr;</italic>(√<italic>n</italic> log<supscrpt>2</supscrpt> <italic>n</italic>). The main tool that we use is spanning trees with low stabbing number, i.e. with the property that no line intersects more than <italic>&Ogr;</italic>(√<italic>n</italic>) edges of the tree. Using such trees we obtain faster algorithms for several other problems, including implicit point location, polygon containment and implicit hidden surface removal.

Ray shooting and other applications of spanning trees with low stabbing number