| 1. |
- Aichholzer, Oswin, et al.
(författare)
-
Bicolored Order Types
- 2024
-
Ingår i: Computing in Geometry and Topology. - 2750-7823. ; 3:2
-
Tidskriftsartikel (refereegranskat)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 that are to the left of an oriented line spanned by two red points or by one red and one blue point in λB. Analogously the number of red points is stored in λR. As a main result, we show that the equivalence of the information contained in the orientation of all bicolored point triples and the two matrices λB and λR also holds in the colored case. This is remarkable, as in general the bicolored order type does not even contain sufficient information to determine all extreme points (points on the boundary of the convex hull of the point set).We then show that the information of a bicolored order type is sufficient to determine whether the two color classes can be linearly separated and how one color class can be sorted around a point of the other color class. Moreover, knowing the bicolored order type of a point set suffices to find bicolored plane perfect matchings or to compute the number of crossings of the complete bipartite graph drawn on a bicolored point set in quadratic time.
|
|
| 2. |
- Aichholzer, Oswin, et al.
(författare)
-
Flips in Odd Matchings
- 2024
-
Ingår i: 40th European Workshop on Computational Geometry. ; , s. 447-452
-
Konferensbidrag (refereegranskat)abstract
- Let P be a set of n = 2m + 1 points in the plane in general position. We define the graph GMP whose vertex set is the set of all plane matchings on P with exactly m edges. Two vertices in GMP are connected if the two corresponding matchings have m − 1 edges in common. In this work we show that GMP is connected.
|
|
| 3. |
- Aichholzer, Oswin, et al.
(författare)
-
Folding Polyominoes into (Poly)Cubes
-
Ingår i: International journal of computational geometry and applications. - 0218-1959.
-
Tidskriftsartikel (refereegranskat)
|
|
| 4. |
|
|
| 5. |
- Aichholzer, Oswin, et al.
(författare)
-
Folding Polyominoes with Holes into a Cube
- 2021
-
Ingår i: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 93
-
Tidskriftsartikel (refereegranskat)abstract
- When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special “basic” holes guarantee foldability.
|
|
| 6. |
- Oswin, Aichholzer, et al.
(författare)
-
Two Equivalent Representations of Bicolored Order Types
- 2023
-
Ingår i: 39th European Workshop on Computational Geometry. ; , s. 12-17
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)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 that are to the left of an oriented line spanned by two red points or by one red and one blue point in λB. Analogously the number of red points is stored in λR.We show that the equivalence of the information contained in the orientation of all bicolored point triples and the two matrices λB and λR also holds in the colored case. This is remarkable, as in general the bicolored order type does not even contain sufficient information to determine all extreme points (points on the boundary of the convex hull of the point set).
|
|
