  For most algorithms dealing with sets of points in the plane, the only
relevant information carried by the input is the combinatorial configuration of
the points: the orientation of each triple of points in the set (clockwise,
counterclockwise, or collinear). This information is called the order type of
the point set. In the dual, realizable order types and abstract order types are
combinatorial analogues of line arrangements and pseudoline arrangements. Too
often in the literature we analyze algorithms in the real-RAM model for
simplicity, putting aside the fact that computers as we know them cannot handle
arbitrary real numbers without some sort of encoding. Encoding an order type by
the integer coordinates of some realizing point set is known to yield doubly
exponential coordinates in some cases. Other known encodings can achieve
quadratic space or fast orientation queries, but not both. In this
contribution, we give a compact encoding for abstract order types that allows
efficient query of the orientation of any triple: the encoding uses O(n^2) bits
and an orientation query takes O(log n) time in the word-RAM model. This
encoding is space-optimal for abstract order types. We show how to shorten the
encoding to O(n^2 (loglog n)^2 / log n) bits for realizable order types, giving
the first subquadratic encoding for those order types with fast orientation
queries. We further refine our encoding to attain O(log n/loglog n) query time
without blowing up the space requirement. In the realizable case, we show that
all those encodings can be computed efficiently. Finally, we generalize our
results to the encoding of point configurations in higher dimension.
