A new discrete theory of pseudoconvexity
Recently geometric hypergraphs that can be defined by intersections of pseudohalfplanes with a finite point set were defined in a purely combinatorial way. This led to extensions of earlier results about points and halfplanes to pseudohalfplanes, including polychromatic colorings and discrete Helly-...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-05-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/9255/pdf |
| _version_ | 1827174051731210240 |
|---|---|
| author | Balázs Keszegh |
| author_facet | Balázs Keszegh |
| author_sort | Balázs Keszegh |
| collection | DOAJ |
| description | Recently geometric hypergraphs that can be defined by intersections of
pseudohalfplanes with a finite point set were defined in a purely combinatorial
way. This led to extensions of earlier results about points and halfplanes to
pseudohalfplanes, including polychromatic colorings and discrete Helly-type
theorems about pseudohalfplanes.
Here we continue this line of research and introduce the notion of convex
sets of such pseudohalfplane hypergraphs. In this context we prove several
results corresponding to classical results about convexity, namely Helly's
Theorem, Carath\'eodory's Theorem, Kirchberger's Theorem, Separation Theorem,
Radon's Theorem and the Cup-Cap Theorem. These results imply the respective
results about pseudoconvex sets in the plane defined using pseudohalfplanes.
It turns out that most of our results can be also proved using oriented
matroids and topological affine planes (TAPs) but our approach is different
from both of them. Compared to oriented matroids, our theory is based on a
linear ordering of the vertex set which makes our definitions and proofs quite
different and perhaps more elementary. Compared to TAPs, which are continuous
objects, our proofs are purely combinatorial and again quite different in
flavor. Altogether, we believe that our new approach can further our
understanding of these fundamental convexity results. |
| first_indexed | 2024-03-11T21:30:33Z |
| format | Article |
| id | doaj.art-214a61e3a8294620aaae5719a399ded2 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2025-03-21T03:49:24Z |
| publishDate | 2023-05-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-214a61e3a8294620aaae5719a399ded22024-07-30T12:11:35ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-05-01vol. 25:1Combinatorics10.46298/dmtcs.92559255A new discrete theory of pseudoconvexityBalázs KeszeghRecently geometric hypergraphs that can be defined by intersections of pseudohalfplanes with a finite point set were defined in a purely combinatorial way. This led to extensions of earlier results about points and halfplanes to pseudohalfplanes, including polychromatic colorings and discrete Helly-type theorems about pseudohalfplanes. Here we continue this line of research and introduce the notion of convex sets of such pseudohalfplane hypergraphs. In this context we prove several results corresponding to classical results about convexity, namely Helly's Theorem, Carath\'eodory's Theorem, Kirchberger's Theorem, Separation Theorem, Radon's Theorem and the Cup-Cap Theorem. These results imply the respective results about pseudoconvex sets in the plane defined using pseudohalfplanes. It turns out that most of our results can be also proved using oriented matroids and topological affine planes (TAPs) but our approach is different from both of them. Compared to oriented matroids, our theory is based on a linear ordering of the vertex set which makes our definitions and proofs quite different and perhaps more elementary. Compared to TAPs, which are continuous objects, our proofs are purely combinatorial and again quite different in flavor. Altogether, we believe that our new approach can further our understanding of these fundamental convexity results.https://dmtcs.episciences.org/9255/pdfmathematics - combinatoricscomputer science - computational geometry |
| spellingShingle | Balázs Keszegh A new discrete theory of pseudoconvexity Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics computer science - computational geometry |
| title | A new discrete theory of pseudoconvexity |
| title_full | A new discrete theory of pseudoconvexity |
| title_fullStr | A new discrete theory of pseudoconvexity |
| title_full_unstemmed | A new discrete theory of pseudoconvexity |
| title_short | A new discrete theory of pseudoconvexity |
| title_sort | new discrete theory of pseudoconvexity |
| topic | mathematics - combinatorics computer science - computational geometry |
| url | https://dmtcs.episciences.org/9255/pdf |
| work_keys_str_mv | AT balazskeszegh anewdiscretetheoryofpseudoconvexity AT balazskeszegh newdiscretetheoryofpseudoconvexity |