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: I try and make my stuff reasonably OS/platform-independent.
gollark: blittle?
gollark: PotatOS has a semi-independent VFS/sandbox library, but I had to add a *lot* of patches for sandbox escapes and stuff to PotatoBIOS, so it's hard to use it separately.
gollark: Unless it doesn't.
gollark: Anyway, many of the bugs in potatOS come from stuff like the SPUDNET daemon not being subject to sandboxing, so people can fake events and stuff going to that in increasingly convoluted ways to make it execute code when it shouldn't.

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.