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

Oswin Aichholzer, Tillmann Miltzow, Alexander Pilz*

*Korrespondierende/r Autor/-in für diese Arbeit

Publikation: Beitrag in einer FachzeitschriftArtikelBegutachtung

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.
Originalspracheenglisch
Seiten (von - bis)518-526
FachzeitschriftComputational Geometry
Jahrgang47
DOIs
PublikationsstatusVeröffentlicht - 2014

Fields of Expertise

  • Information, Communication & Computing

Treatment code (Nähere Zuordnung)

  • Theoretical
  • Basic - Fundamental (Grundlagenforschung)

Fingerprint

Untersuchen Sie die Forschungsthemen von „Reprint of: Extreme points and halving edge search in abstract order types“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren