Bicolored Order Types
Abstract: In their seminal work on Multidimensional Sorting, Goodman and Pollack introduced the so-called order type, which for each ordered triple of a point set in the plane gives its orientation, clockwise or counterclockwise. This information is sufficient to solve many problems from discrete geometry where properties of point sets do not depend on the exact coordinates of the points but only on their relative positions. Goodman and Pollack showed that an efficient way to store an order type in a matrix λ of quadratic size (w.r.t. the number of points) is to count for every oriented line spanned by two points of the set how many of the remaining points lie to the left of this line. We generalize the concept of order types to bicolored point sets (every point has one of two colors). The bicolored order type contains the orientation of each bicolored triple of points, while no information is stored for monochromatic triples. Similar to the uncolored case, we store the number of blue points.... https://www.cgt-journal.org/index.php/cgt/article/view/46
- Location
-
Deutsche Nationalbibliothek Frankfurt am Main
- Extent
-
Online-Ressource
- Language
-
Englisch
- Bibliographic citation
-
Bicolored Order Types ; volume:3 ; number:2 ; year:2024
Computing in Geometry and Topology ; 3, Heft 2 (2024)
- Creator
-
Aichholzer, Oswin
Brötzner, Anna
- DOI
-
10.57717/cgt.v3i2.46
- URN
-
urn:nbn:de:101:1-2024030306541463052540
- Rights
-
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Last update
-
14.08.2025, 11:02 AM CEST
Data provider
Deutsche Nationalbibliothek. If you have any questions about the object, please contact the data provider.
Associated
- Aichholzer, Oswin
- Brötzner, Anna
Other Objects (12)
Logic programming over polymorphically order-sorted types
Partial order semantics of types of Nets
Advantages of Types in Partial-Order Planning
Well-partial orderings and their maximal order types
Investigating interactions between types of order in categorization
Types, Abstraction and Parametric Polymorphism in Higher-Order Logic
Higher-Order PLS-PM Approach for Different Types of Constructs
Simplification orders in term rewriting : derivation lengths, order types, and computability
Kamenev and Philos-types oscillation criteria for fourth-order neutral differential equations
Coexistence of two types of short-range order in Si–Ge–Sn medium-entropy alloys
Function-based hybrid synchronization types and their coexistence in non-identical fractional-order chaotic systems
Types annamites
Logic programming over polymorphically order-sorted types
Partial order semantics of types of Nets
Advantages of Types in Partial-Order Planning
Well-partial orderings and their maximal order types
Investigating interactions between types of order in categorization
Types, Abstraction and Parametric Polymorphism in Higher-Order Logic
Higher-Order PLS-PM Approach for Different Types of Constructs
Simplification orders in term rewriting : derivation lengths, order types, and computability
Kamenev and Philos-types oscillation criteria for fourth-order neutral differential equations
Coexistence of two types of short-range order in Si–Ge–Sn medium-entropy alloys
Function-based hybrid synchronization types and their coexistence in non-identical fractional-order chaotic systems
Types annamites
Logic programming over polymorphically order-sorted types
Partial order semantics of types of Nets
Advantages of Types in Partial-Order Planning
Well-partial orderings and their maximal order types
Investigating interactions between types of order in categorization
Types, Abstraction and Parametric Polymorphism in Higher-Order Logic
Higher-Order PLS-PM Approach for Different Types of Constructs
Simplification orders in term rewriting : derivation lengths, order types, and computability
Kamenev and Philos-types oscillation criteria for fourth-order neutral differential equations
Coexistence of two types of short-range order in Si–Ge–Sn medium-entropy alloys
Function-based hybrid synchronization types and their coexistence in non-identical fractional-order chaotic systems