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

Convex hulls are a fundamental geometric tool used in a number of algorithms.A famous paper by Akl and Toussaint in 1978 described a way to reduce thenumber of points involved in the computation, which is since known as theAkl-Toussaint heuristics. This paper first studies what this heurstics reallyrepresents in terms of reduction of points and demonstrates that the optimumselection is reached using an octogon as the remaining number of points is inO(sqrt(N)) rather than the usual O(N). Then it focuses on optimising theoverall computational efficiency in a convex hull computation. Although theheuristics is usually used as a first step in computations one can obtain theconvex hull directly from the heuristics's basis. First a simple incrementalimplementation is described, and if the number of characteristic points of theAkl-Toussaint heuristics p is taken as a parametre the convex hull is thencomputed in a O(N(p+h/p)) average complexity or O(Nh) asymptotic complexity.Given the relative constant factor of 1/p however experimental results showthat this algorithm should be considered linear in average. Worst-casecomplexity is in O(N^2) and space complexity is O(h) but could be O(1) if therequired output is the array of convex vertices's indexes. Then a remark on whythe basic incremental method should be preferred for average cases is made.Finally an optimal linear algorithm both in average and worst-case and using aminimal space complexity in O(sqrt(N)) in average (or O(1) if in-placecomputation is allowed) is presented.

Convex hull: Incremental variations on the Akl-Toussaint heuristics Simple, optimal and space-saving convex hull algorithms