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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

An arrangement of n lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists of &Ogr;(n2) regions, called faces. In this paper we study the problem of calculating and storing arrangements implicitly, using subquadratic space and preprocessing, so that, given any query point p, we can calculate efficiently the face containing p. First, we consider the case of lines and show that with &Lgr;(n) space1 and &Lgr;(n3/2) preprocessing time, we can answer face queries in &Lgr;(√n) + &Ogr;(K) time, where K is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: 1) given a set of n points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, 2) given a simple polygonal path &Ggr;, form a data structure from which we can find the convex hull of any subpath of &Ggr; quickly, and 3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a trade-off between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in &Lgr;(n1/3) time, given &Lgr;(n4/3) space and &Lgr;(n5/3) preprocessing time. Lastly, we note that our techniques allow us to compute m faces in an arrangement of n lines in time &Lgr;(m2/3n2/3 + n), which is nearly optimal.

Implicitly representing arrangements of lines or segments