Coordinate representation of order types requires exponential storage
JE Goodman, R Pollack, B Sturmfels - … of the twenty-first annual ACM …, 1989 - dl.acm.org
JE Goodman, R Pollack, B Sturmfels
Proceedings of the twenty-first annual ACM symposium on Theory of computing, 1989•dl.acm.orgWe give doubly exponential upper and lower bounds on the size of the smallest grid on
which we can embed every planar configuration of n points in general position up to order
type. The lower bound is achieved by the construction of a widely dispersed “rigid”
configuration which is then modified to one in general position by recent techniques of
Sturmfels and White, while the upper bound uses recent results of Grigor'ev and Vorobjou
on the solution of simultaneous inequalities. This provides a sharp answer to a question first …
which we can embed every planar configuration of n points in general position up to order
type. The lower bound is achieved by the construction of a widely dispersed “rigid”
configuration which is then modified to one in general position by recent techniques of
Sturmfels and White, while the upper bound uses recent results of Grigor'ev and Vorobjou
on the solution of simultaneous inequalities. This provides a sharp answer to a question first …
We give doubly exponential upper and lower bounds on the size of the smallest grid on which we can embed every planar configuration of n points in general position up to order type. The lower bound is achieved by the construction of a widely dispersed “rigid” configuration which is then modified to one in general position by recent techniques of Sturmfels and White, while the upper bound uses recent results of Grigor'ev and Vorobjou on the solution of simultaneous inequalities. This provides a sharp answer to a question first posed by Chazelle.
ACM Digital Library