Reprint of: Extreme points and halving edge search in abstract order types

Oswin Aichholzer, Tillmann Miltzow, Alexander Pilz*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the setʼs chirotope, as a source of information. We answer this question in the affirmative. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time. We first give a proof for sets realizable in the Euclidean plane and then extend the result to non-realizable abstract order types.
Original languageEnglish
Pages (from-to)518-526
JournalComputational Geometry
Volume47
Issue number3
DOIs
Publication statusPublished - 2014

Fields of Expertise

  • Information, Communication & Computing

Treatment code (Nähere Zuordnung)

  • Theoretical
  • Basic - Fundamental (Grundlagenforschung)

Fingerprint

Dive into the research topics of 'Reprint of: Extreme points and halving edge search in abstract order types'. Together they form a unique fingerprint.

Cite this