Extreme point and halving edge search in abstract order types

DOI10.1016/J.COMGEO.2013.05.001MaRDI QIDQ2391543zbMATH OpenOpenAlexWikidataFDO

Authors Tillmann Miltzow, Alexander Pilz, Oswin Aichholzer

Publication date 31 July 2013

Published in Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0925772113000394

zbMATH Keywords

abstract order typealgorithmCC systemchirotopecomputational geometryconvex hullhalving line

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• The Complexity of Order Type Isomorphism
• An optimal algorithm for reconstructing point set order types from radial orderings
• On k-Hulls and Related Problems

Cites work

• A theorem of ordered duality
• Abstract order type extension and new results on the rectilinear crossing number
• Algorithms for ham-sandwich cuts
• Axioms and hulls
• Geodesic order types
• Multidimensional Sorting
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines
• Semispaces of configurations, cell complexes of arrangements
• The Ultimate Planar Convex Hull Algorithm?
• Time bounds for selection

Cited in

(5)

• Realization spaces of arrangements of convex bodies
• An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings
• Reprint of: Extreme point and halving edge search in abstract order types
• Subquadratic encodings for point configurations
• Geodesic-preserving polygon simplification

This page was built for publication: Extreme point and halving edge search in abstract order types

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2391543)