---
# System prepended metadata

title: 'Goal: write out any given word with less than 100 stickers'

---

# Goal: write out any given word with less than 100 stickers
we have rectangle stickers, circle stickers, etc...
## Approaches
1. gradient descent
I'm just not good enough to generate a good enough result.
2. rectilinear polygon cover problem
Papers
root
https://link.springer.com/content/pdf/10.1007/BF02523677.pdf
annotation 18 ->

https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1056648

annotation 19 ->
probably not related, it has something to do with recognizing 2d primitive shapes in 3d.

back to root
https://link.springer.com/content/pdf/10.1007/BF02523677.pdf
annotation 14 -> probably shows that interior cover problem with holes are NP-complete

Since most rectilinear cover problems are NP-hard
Some papers are about finding polynomial solutions to special cases of the cover problems.
annotation 9 ->

covering convex rectilinear polygons in linear time
https://www.worldscientific.com/doi/pdf/10.1142/S0218195991000128
define: a rectilinear polygon is a finite set of unit squares.
define convex rectilinear polygons:
a rectilinear polygon is convex if:
any two unit square in B on the same horizontal or vertical line, all unit squares between them are also in B.
## My thoughts here
maybe we can try to partition a word into convex rectilinear polygons by the following simple method:
pick a black pixel where it has one side touching white pixel, draw a line in the opposite way until touching white pixel......
picture:
![](https://i.imgur.com/M630Mhv.jpg)


https://github.com/mittalgovind/Polygon-Partition
this is done before immma redo it in c++ to make sure i understand what i am doing