Determining sign(det(A)) for nearly-singular matrix A

Motivation: determining whether a point $p$ is above or below a plane $\pi$, which is defined by $d$ points, in a $d$-dimensional space, is equivalent to computing the sign of a determinant of a matrix of the form

A = $\begin{pmatrix}p_{1}^{\left(1\right)} & p_{1}^{\left(2\right)} & \cdots & p_{1}^{\left(d\right)} & 1\\ p_{2}^{\left(1\right)} & p_{2}^{\left(2\right)} & \cdots & p_{2}^{\left(d\right)} & 1\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ p_{d}^{\left(1\right)} & p_{d}^{\left(2\right)} & \cdots & p_{d}^{\left(d\right)} & 1\\ p^{\left(1\right)} & p^{\left(2\right)} & \cdots & p^{\left(d\right)} & 1 \end{pmatrix}$

Notes -

1. When I say sign, I mean either negative, positive, or exactly zero
2. The entry ${p_i}^j$ means the $j$-coordinate (e.g., $x$, $y$ and $z$ when $d$=3) of the $i$'th point in my problem. The matrix is not a Vandermonde matrix.

The resulting matrix is composed of floating-point numbers. It has no special structure, is not diagonally dominant, is not symmetric, and has no special reason to be positive-semidefinite. It might be sparse, though.

It is, however, many times nearly singular.

I'm interested in computing $\mbox{sign}(|A|)$ in a fast and robust way.

Since this is Math-SE, I'm mainly asking if there are any spectral theorems which allow this computation without explicitly computing the determinant. For example, the Greshgorin Circle Theorem could be very useful if $A$ was diagonally-dominant. Alternatively, any cheap test to identify some cases would also be helpful.

-
It seems to be a variant of the Vandermonde matrix. –  Pedro Tamaroff Dec 17 '12 at 1:30
@Potato Right. When I say variant I mean it is not in the exact form. –  Pedro Tamaroff Dec 17 '12 at 1:35
@Potato It's not a Vandermonde matrix: the superscripts are identifying the coordinates of the $d$ points $p_1, \dots, p_d$ that are known to lie in the plane--they are not powers. –  Jonathan Christensen Dec 17 '12 at 1:38
There is something not clear. Do you perform this task for just one test point $p$ for each set of $d$ points? If not, you find a normal $N$ to the hyperplane and see how $p \cdot N$ compares with $p_1 \cdot N$ for each new $p.$ –  Will Jagy Dec 17 '12 at 1:53
In that case, I would say your actual task is rather more elaborate than a single determinant, and you need to think out what happens when replacing points. –  Will Jagy Dec 17 '12 at 2:11