Minimum covering polyplet
A minimum covering polyplet (MCP) of a pattern is a polyplet (i.e. orthogonally/diagonally connected pattern) of minimal population covering said pattern.[1] The minimum covering polyplet size (MCPS) of a pattern is the size of a minimum covering polyplet[1]; unlike the minimum covering polyplet itself, this is a single, well-defined number.
There is one pattern with MCPS = 1, two patterns with MCPS = 2, 8 patterns with MCPS = 3, and 39 patterns with MCPS = 4 (not distinguishing between different orientations).[2][3]
Computation
Finding a minimum covering polyplet for a given pattern is an instance of the Steiner tree problem[4],[1] which is NP-hard[5]; however, finding a minimum covering polyplet for a given small pattern is often easy in practice.
Uses
Oscar Cunningham proposed using the minimum covering polyplet size to gauge the size of a methuselah, as it penalizes both population and bounding box.[6] The resulting metric is L/MCPS.
References
- ↑ 1.0 1.1 1.2 Oscar Cunningham (January 20, 2018). Re: Largest and oldest methuselah ever found! (discussion thread) at the ConwayLife.com forums
- ↑ Oscar Cunningham (October 26, 2022). Re: Thread for basic questions (discussion thread) at the ConwayLife.com forums
- ↑ confocaloid (March 8, 2023). Re: Search Requests Thread (discussion thread) at the ConwayLife.com forums
- ↑ Steiner tree problem at Wikipedia
- ↑ NP-hard problem
- ↑ Oscar Cunningham (January 20, 2018). Re: Largest and oldest methuselah ever found! (discussion thread) at the ConwayLife.com forums