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.

Computation

Finding a minimum covering polyplet for a given pattern is an instance of the Steiner tree problem,[1] which is NP-hard; 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.[2] The resulting metric is L/MCPS.

gollark: Hello, can I advertise potatOS to you (available at this link)? It's a useless OS with useless features which is slightly annoying to remove.
gollark: BANNED, not informed consent.
gollark: Especially given that it has many cases which are not very special.
gollark: ```Admins and moderators interpret the rules. You cannot argue about special cases.```Yet another ridiculous bit.
gollark: ```Advertising or installing software that could be considered malicious or dangerous without the player’s informed consent is forbidden.```Wait, so... to advertise stuff... you need informed consent... but you can't inform them?

References
  1. Oscar Cunningham (January 20, 2018). Re: Largest and oldest methuselah ever found! (discussion thread) at the ConwayLife.com forums
  2. Oscar Cunningham (January 20, 2018). Re: Largest and oldest methuselah ever found! (discussion thread) at the ConwayLife.com forums
This article is issued from Conwaylife. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.