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

Given $n$ points in the plane, we propose algorithms to compile connectedcrossing-free geometric graphs into directed acyclic graphs (DAGs). The DAGsallow efficient counting, enumeration, random sampling, and optimization. Ouralgorithms rely on Wettstein's framework to compile several crossing-freegeometric graphs. One of the remarkable contributions of Wettstein is to allowdealing with geometric graphs with connectivity, since it is known to bedifficult to efficiently represent geometric graphs with such global property.To achieve this, Wettstein proposed specialized techniques for crossing-freespanning trees and crossing-free spanning cycles and invented compilingalgorithms running in $\mathrm{O}(7.044^n)$ time and $\mathrm{O}(5.619^n)$time, respectively.  Our first contribution is to propose a technique to deal with theconnectivity constraint more simply and efficiently. It makes the design andanalysis of algorithms easier, and yields improved time complexity. Ouralgorithms achieve $\mathrm{O}(6^n)$ time and $\mathrm{O}(4^n)$ time forcompiling crossing-free spanning trees and crossing-free spanning cycles,respectively. As the second contribution, we propose an algorithm to optimizethe area surrounded by crossing-free spanning cycles. To achieve this, wemodify the DAG so that it has additional information. Our algorithm runs in$\mathrm{O}(4.829^n)$ time to find an area-minimized (or maximized)crossing-free spanning cycle of a given point set. Although the problem wasshown to be NP-complete in 2000, as far as we know, there were no knownalgorithms faster than the obvious $\mathrm{O}(n!)$ time algorithm for 20years.

Compiling Crossing-free Geometric Graphs with Connectivity Constraint for Fast Enumeration, Random Sampling, and Optimization