Extreme point and halving edge search in abstract order types

Goodman, 1983, Multidimensional sorting, SIAM J. Comput., 12, 484, 10.1137/0212032 Goodman, 1984, Semispaces of configurations, cell complexes of arrangements, J. Combin. Theory Ser. A, 37, 257, 10.1016/0097-3165(84)90050-5 Knuth, 1992, Axioms and Hulls, vol. 606 Guibas, 1985, Primitives for the manipulation of general subdivisions and computation of Voronoi diagrams, ACM Trans. Graph., 4, 74, 10.1145/282918.282923 Aichholzer, 2007, Abstract order type extension and new results on the rectilinear crossing number, Comput. Geom., 36, 2, 10.1016/j.comgeo.2005.07.005 Goodman, 1980, Proof of Grünbaumʼs conjecture on the stretchability of certain arrangements of pseudolines, J. Combin. Theory Ser. A, 29, 385, 10.1016/0097-3165(80)90038-2 Lo, 1994, Algorithms for ham-sandwich cuts, Discrete Comput. Geom., 11, 433, 10.1007/BF02574017 Kirkpatrick, 1986, The ultimate planar convex hull algorithm?, SIAM J. Comput., 15, 287, 10.1137/0215021 Habert, 2004, Computing the convex hull of discs using only their chirotope, 111 Aichholzer, 2012, Geodesic order types, vol. 7434, 216 Miltzow, 2012, Selection of extreme points and halving edges of a set by its chirotope, 85 Blum, 1973, Time bounds for selection, J. Comput. System Sci., 7, 448, 10.1016/S0022-0000(73)80033-9 Asinowski, 2013, Quasi-parallel segments and characterization of unique bichromatic matchings, 225 Levi, 1926, Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade, Ber. Math.-Phys. Kl. Sächs. Akad. Wiss. Leipzig, 78, 256 Goodman, 1982, A theorem of ordered duality, Geom. Dedicata, 12, 63, 10.1007/BF00147331 Chan, 1996, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete Comput. Geom., 16, 361, 10.1007/BF02712873