Geometry / Hull (Bibtex)

P511: Enumerate all maximal obstacle-free convex hulls

Input:

A set $V$ of points and a set $X$ of obstacles.

Output:

All maximal obstacle-free convex hulls.

Complexity:

$O(|V|^2|X| (|X| + \log |V|)$ delay.

Comment:

Exponential space. Proximity search.

Reference:

[Conte2019] (Bibtex)