Unless you have some additional structure on the points $A_1$,...,$A_n$ your problem is as hard (and as easy) as computing the convex hull of $2n$ points in $\mathbb{R}^n$, and triangulating this convex hull.