Point Location on A Convex Hull (PHULL)
Category: Geometry
Input
An integer $d$, a set $S$ of $n$ points in $\Q^d$, and a designated point $p \in \Q^d$.
Problem
Is $p$ on the convex hull of $S$?
Status
$\P$-complete (Long and Warmuth [1]).
Remarks
The reduction to show hardness is from MCVP.
The result shows that SCH, for arbitrary dimension $d$ is $\P$-complete. The convex hull of $n$ points in the Euclidean plane can be computed optimally on an EREW-PRAM in $O(\log n)$ time using $n$ processors (see Dessmark, Lingas, and Maheshwari [2]).
References
- P. M. Long and M. K. Warmuth (1994). Composite geometric concepts and polynomial predictability.
- A. Dessmark, A. Lingas, and A. Maheshwari (1979). Multi-list ranking: complexity and applications.
- H. J. Hoover (1991). Real functions, contraction mappings, and P-completeness.
- H. J. Hoover (1990). Feasible real functions and arithmetic circuits.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.9.4.