Pebble sets in convex polygons
Extremal set theory (05D05) Convex sets in (2) dimensions (including convex curves) (52A10) Helly-type theorems and geometric transversal theory (52A35) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational aspects related to convexity (52B55)
A pebble set in a convex \(n\)-gon \(P\) is a set \(S\) of \(n-2\) points in the interior of \(P\) so that every triangle determined by vertices of \(P\) contains exactly one point of \(S\) in its interior. A pebble set is called peripheral if each of its points lies in a triangle formed by three consecutive vertices of \(P\). The authors show that all pebble sets of a regular \(n\)-gon are peripheral and give examples of polygons where there are other pebble sets. They characterize all peripheral pebble sets and obtain as a corollary the number of peripheral pebble sets in an \(n\)-gon for \(n\geq 4\), namley \(n2^{n-5}\). Instead of the points of pebble sets one may equivalently consider so-called chambers. These are maximal connected subsets of the polygon that do not intersect any edges or chords of the polygon. Thus any point of a pebble set may be replaced by an arbitrary point lying in the same chamber. The authors provide a characterization of the chambers which may contain a point of a pebble set. This leads also to an algorithm for determining all such chambers.
- Convex Sets and Polygons
- Convex hulls of polyominoes
- Pebbling in Hypercubes
- Convex polyominoes and heaps of segments
- scientific article; zbMATH DE number 2156778
- The convex hull of a set of convex polygons
- scientific article; zbMATH DE number 1440118
- Polyhedron approximation of tile set
- Cover pebbling hypercubes
This page was built for publication: Pebble sets in convex polygons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2471724)
