Javascript must be enabled to continue!
Pin the loop taut: a one-player topologame
View through CrossRef
Abstract
We introduce a 1-player game called pin the loop and analyse its complexity. A loop is a generic immersion of the circle in a surface, considered up to isotopy. A loop is taut when it is minimally intersecting in its homotopy class. A pinning set of a loop is a set of points P in the surface avoiding the loop, such that the loop is taut in the surface punctured at P. The pinning number is the minimal cardinal of its pinning sets, and a pinning set is optimal if it has that cardinal.
We show that the decision problem associated to computing the pinning number of a plane loop is NP-complete. We implement a polynomial algorithm to check if a given point-set is pinning, adapting a method of Birman--Series for computing intersection numbers of curves in surfaces. After improving a theorem of Hass--Scott characterising taut loops in surfaces, we reduce the problem to a boolean formula whose solutions correspond to the pinning sets. Finally, we reduce the vertex-cover problem for graphs to an instance of the pinning problem for plane loops.
Our results imply that given a closed geodesic in a complete Riemannian surface with punctures, it is hard to guess the location of the punctures from the sole isotopy class of the geodesic in the compactified surface.
Title: Pin the loop taut: a one-player topologame
Description:
Abstract
We introduce a 1-player game called pin the loop and analyse its complexity.
A loop is a generic immersion of the circle in a surface, considered up to isotopy.
A loop is taut when it is minimally intersecting in its homotopy class.
A pinning set of a loop is a set of points P in the surface avoiding the loop, such that the loop is taut in the surface punctured at P.
The pinning number is the minimal cardinal of its pinning sets, and a pinning set is optimal if it has that cardinal.
We show that the decision problem associated to computing the pinning number of a plane loop is NP-complete.
We implement a polynomial algorithm to check if a given point-set is pinning, adapting a method of Birman--Series for computing intersection numbers of curves in surfaces.
After improving a theorem of Hass--Scott characterising taut loops in surfaces, we reduce the problem to a boolean formula whose solutions correspond to the pinning sets.
Finally, we reduce the vertex-cover problem for graphs to an instance of the pinning problem for plane loops.
Our results imply that given a closed geodesic in a complete Riemannian surface with punctures, it is hard to guess the location of the punctures from the sole isotopy class of the geodesic in the compactified surface.
Related Results
Myogenic differentiation induces taurine transporter in association with taurine-mediated cytoprotection in skeletal muscles
Myogenic differentiation induces taurine transporter in association with taurine-mediated cytoprotection in skeletal muscles
Skeletal muscle homoeostasis is maintained by a variety of cytoprotective mechanisms. Since ablation of the TauT (taurine transporter) gene results in susceptibility to exercise-in...
A Single Channel Thermal-Hydraulic Calculation Module for PWR Pin-by-Pin Wise Coupled Calculation System
A Single Channel Thermal-Hydraulic Calculation Module for PWR Pin-by-Pin Wise Coupled Calculation System
Abstract
Due to the strong feedback effect between neutronics and thermal-hydraulics in the core of pressurized water reactors (PWR), neutronics and thermal-hydrauli...
Cam Design and Pin Defect Detection of Cam Pin Insertion Machine in IGBT Packaging
Cam Design and Pin Defect Detection of Cam Pin Insertion Machine in IGBT Packaging
Packaging equipment plays a crucial role in the semiconductor industry by enhancing product quality and reducing labor costs through automation. Research was conducted on IGBT modu...
Material Flow Interaction in Multi-Pin Extrusion: A Study on Pin Height Variability and Process Predictability
Material Flow Interaction in Multi-Pin Extrusion: A Study on Pin Height Variability and Process Predictability
The increasing demand for lightweight multi-material structures, particularly in automotive and aerospace applications, requires robust and efficient joining technologies. Mechanic...
Additively-Separable Sum Linear Programming Games
Additively-Separable Sum Linear Programming Games
We introduce the class of additively-separable linear-programming games. Such games are two-person/two-player games, where one player’s “strategy set” is a “closed convex polytope”...
Pin-on-Plate vs. Pin-on-Disk Wear Tests: Theoretical and Numerical Observations on the Initial Transient Phase
Pin-on-Plate vs. Pin-on-Disk Wear Tests: Theoretical and Numerical Observations on the Initial Transient Phase
Pin-on-plate and pin-on-disk wear tests are typically used for assessing the wear behavior of a given material coupling and estimating its wear coefficient using the Archard wear l...
Effect of Pin Speed on Cerchar Abrasion Test Results
Effect of Pin Speed on Cerchar Abrasion Test Results
Abstract
Abrasive properties of rocks affect tool selection and design of rock excavation machines as well as their productivity and operational costs. The Cerchar t...

