# Residual-guided Personalized Speech Synthesis Based on Face Image

###### Abstract

Previous works derive personalized speech features by training the model on a
large dataset composed of his/her audio sounds. It was reported that face
information has a strong link with the speech sound. Thus in this work, we
innovatively extract personalized speech features from human faces to
synthesize personalized speech using neural vocoder. A Face-based Residual
Personalized Speech Synthesis Model (FR-PSS) containing a speech encoder, a
speech synthesizer and a face encoder is designed for PSS. In this model, by
designing two speech priors, a residual-guided strategy is introduced to guide
the face feature to approach the true speech feature in the training.
Moreover, considering the error of feature’s absolute values and their
directional bias, we formulate a novel tri-item loss function for face
encoder. Experimental results show that the speech synthesized by our model is
comparable to the personalized speech synthesized by training a large amount
of audio data in previous works.

Index Terms—  Personalized speech synthesis, Speech prior, Residual, Attention
mechanism

##  1 Introduction

Generating natural speech from text (text-to-speech synthesis, TTS) has been
studied for decades [1, 2, 3]. Tacotron [1] and Tacotron 2 [2] are two
efficient end-to-end speech synthesis models for TTS based on deep learning.
As for the personalized speech synthesis of multiple speakers, Google proposed
a system [4] that used several audio datasets to train a speaker encoder with
a sequence-to-sequence TTS network and the vocoder based on Tacotron2.
Besides, Baidu’s deepvoice3 [5] added a speaker encoder on the basis of
Tacotron to characterize the timbre characteristics of speakers.

Most of current works extracted personalized speech features based on a large
volume of audio signals. Recently, some research works on speech to face
generation using deep learning methods have emerged [6, 7, 8]. Motivated by
these promising results, we believe that the inverse direction, i.e., the
personalized speech synthesis from one’s face image is feasible. Face2Speech
[9] is the method to predict speech features from face images and then
synthesize speech using the WORLD vocoder [10]. However, it was reported in
[5] that WORLD vocoder introduces various noticeable artifacts, and the
WaveNet vocoder sounds more natural. Besides, [9] only performed qualitative
experiments without quantitative experiments, thus lacking objective
evaluation criteria.

In this work, we propose a novel speaker-independent Face-based Residual
Personalized Speech Synthesis Model (FR-PSS) within an encoder-decoder
architecture, which extracts personalized information from the face image, and
synthesizes audio speech using natural vocoder. An overview of our proposed
FR-PSS is shown in Fig. 1. Firstly, the speech encoder is trained to extract
features from speech. Secondly, the speech synthesizer is trained to
synthesize speech from a given text and features generated from the pre-
trained speech encoder. Thirdly, the face encoder is trained with the pairs of
face image and speech for making features extracted from a face image of a
speaker closer to one derived from his/her speech. The tri-item loss function
and a residual-guided strategy is introduced in this step. Finally, the face
encoder and speech synthesizer are concatenated for building our FR-PSS model.
Compared with Face2Speech, we conduct a series of quantitative experiments.
Experimental results show that our FR-PSS achieves a comparable performance
compared with method that synthesizes personalized speech using a speech-
derived embedding vector.

Overall, our contributions can be summarized as follows. i) A new speech
synthesis model FR-PSS is proposed. We extract personalized speech features
from human faces to synthesize personalized speech using neural vocoder. ii) A
residual-guided strategy is designed by incorporating a prior speech feature
to make the network capture more representative face features and improve
model learning efficiency. iii) We innovatively establish a tri-item loss
function to accelerate training convergence.

##  2 Face-based Residual Personalized Speech Synthesis Model

Fig. 1: Overview of our FR-PSS with the prior speech.

In this section, we will introduce the proposed FR-PSS (shown in Fig. 1),
which includes Speech Encoder (SE), Speech Synthesizer (SS), Face Encoder
(FE), Residual-guided strategy and tri-item loss function, respectively.

###  2.1 Speech Encoder and Speech Synthesizer

SE is to extract speech features. Similar to [11], we apply a network that
maps a sequence of Mel spectrogram frames calculated from speech to a fixed-
dimensional embedding vector. The 40-channel Mel spectrogram is fed to the
network, which is composed of three LSTM layers with a total of 768 units, and
after each layer, there is a 256-dimensional projection. In the inference
process, each utterance of speakers is divided into 800ms windows with 50%
overlapping. The network runs independently on each window, and generates the
final speech embedding by the average and normalization. We use generalized
end-to-end speaker verification losses to train the network.

As for the SS, we use Tacotron 2 model, which includes an encoder and a
decoder that introduces an location sensetive attention. The details can be
referred to [2]. The pretrained WaveRNN in [12] is exploited as the vocoder in
this work.

###  2.2 Face Encoder

We use FE to extract face features which is used to synthesize speech. It is a
four convolution blocks structure, which stacks the convolution kernel of size
1$\times$1, 3$\times$3 and pooling operations. The dimension of the output
feature maps after these three operations are the same, so that we can add
them in the channel dimension. This can increase the network’s width and
improve its adaptability to scale. ReLU operation is performed after each
convolution layer to increase the non-linear character of the network.
Finally, a 256-dimensional embedding is achieved by using a 1$\times$1
convolution.

To make FE owes an ability to focus on face features and ignore the background
noise, we utilize a lightweight general purpose module CBAM [13], which can be
easily integrated into an end-to-end CNN architecture. CBAM contains a channel
and a spatial attention, which are embedded into decoder. Besides, we also
tried channel-focused attention mechanism [14], and it turns out that CBAM
performs better.

###  2.3 Residual-guided Strategy

Due to natural mismatch between face image and speech, it is hard to extract
complete speech features from face image. Therefore, we add a prior
information to help FE extract speech features. By introducing the prior
speech feature, we exploit the idea of the residual to remove the main similar
part of the speech (i.e., prior speech feature), thereby highlighting subtle
changes depicted by speech feature. It is to reduce the training difficulties
and learn more representative speech features. Our FR-PSS converts the face
image to speech by a network $\phi$:
$\phi(f,t)=SS\left(FE(f)+t+s_{prior}\right)$, where $SS$ is the speech
synthesizer, $t$ is the text, $f$ means the image of input face, and
$s_{prior}$ is the prior speech feature calculated before the training stage.

Two speech priors are investigated in this work. The first one is neutral
speech prior, which is the arithmetic mean of a large gender-balance speech
dataset111The dataset contains the same number of male and female speakers.:
$s_{prior}=\frac{1}{n}\sum_{i=1}^{n}{{SE}}(s)$, where $s$ denotes the audio
clips and $n$ is the number of speaker. SE is a CNN structure to extract
speech feature by taking $n$ = 10, 50, 100, 500, and 1000. In this work, we
finally take $n$ equals 500.

The second prior speech feature is gender-dependent prior by assigning two
prior speech features to males and females, respectively. To achieve this, a
robust classifier network is first needed to predict the gender based on the
face image. We use a gender prediction network [15] to predict the gender of
speakers. It is trained on the Adience dataset [16] and tested on VGGFace2
dataset [17].

###  2.4 Tri-item Loss Function

In order to make FE extract the personalized facial features better, we
formulate a tri-item loss function, which is composed of $L_{2}$ loss, the
negative cosine similarity loss and the triplet loss [18].

We consider that $L_{2}$ loss can be used to measure the error between facial
features and speech features and improve the perceptual similarity at the
abstract level. The negative cosine similarity is introduced to make speech
features and face features vectors similar in direction. The triplet loss is
to make the distance between speech feature and the corresponding face feature
vectors closer, and make the distance between the speech feature vector and
the irrelevant face feature vectors farther. The loss function is given as:

$\begin{split}L_{Total}&=1-\frac{\sum_{i=1}^{n}A_{i}\times
B_{i}}{\sqrt{\sum_{i=1}^{n}A_{i}^{2}}\times\sqrt{\sum_{i=1}^{n}B_{i}^{2}}}+\frac{\sum_{i=1}^{n}(A_{i}-B_{i})^{2}}{n}\\\
&+max(d(A,B)-d(A,C),0),\end{split}$ (1)

where $d$ denotes distance of embedding vectors, $A$ and $B$ are the speech
feature and the corresponding face feature embedding vectors. $C$ is the face
feature vector of the irrelevant speaker, and $n$ represents the dimension of
the feature vector.

##  3 Experiment

###  3.1 Datasets

Three public datasets are used to train the proposed FR-PSS:

For the SE, we use the Voxceleb2 [19], which contains 6000 celebrities that
contribute more than one million utterances. We reduce the audio sampling rate
to 16 kHz and divide it into three subsets (i.e., training, validation and
test). Note that there is no speaker overlapped among these three subsets for
all experimental setup in this work.

For the SS, we use LibriTTS [20] consisting of two training sets, which
contains 436 hours of audio speech uttered by 1172 English speakers, with a
sampling frequency of 16 kHz.

As for the FE, we use the voice recording from the Voxceleb2 dataset and the
face images from the manually filtered version of VGGFace2 [17] dataset. We
select an intersection of the two datasets with the common identities and
eliminate non-English speakers, deriving 149,354 voice recordings and 139,572
face images of 1089 subjects. The ratio of our training set to our test set is
8:2.

###  3.2 Implementation Details

We introduce the implementation details for SE, SS and FE, respectively.

First, we use the Voxceleb2 dataset to train the SE. Our model is implemented
by PyTorch 1.1.0 with GPU Tesla K80, and is optimized by Adam with the
learning rate of 0.001 and the exponentially decay rate of 0.9 at every 5
epochs. We train our model with 1.56M steps and batch size 64. The number of
utterance is 10 per speaker.

Secondly, based on the LibriTTS [20], we first train the speech synthesizer
network, and then train the WaveRNN [12] based on the output of the speech
synthesizer network. At the speech synthesizer decoder side, the ground truth
is passed in rather than the predicted results. The batch size is 64, and we
use the Adam optimizer with $\beta_{1}=0.9$, $\beta_{2}=0.999$ and
$\epsilon=10^{-6}$. The initial value of the learning rate is $10^{-3}$, and
the exponential drops to $10^{-5}$ after 50,000 iterations. The pretrained
WaveRNN in [12] is exploited as the vocoder in this work.

Lastly, we use the spectrogram and face-image pairs to train the FE. The FE is
optimized by Adam and the learning rate of 0.01 with the exponentially decay
rate of 0.9 at every 5 epochs. We finally train our model with 50 epochs, and
the batch size is 8.

###  3.3 Evaluation Metrics

To evaluate the quality of speech synthesized by the FR-PSS quantitatively, we
compare speech features extracted from the generated audio and the original
audio, using the $L_{1}$, $L_{2}$ and Cosine Similarity loss ($Cos$). When
$L_{1}$ and $L_{2}$ tends to 0 or $Cos$ tends to 1, the difference between two
features are similar in the direction. Besides, we rely on Mean Opinion Score
(MOS) evaluations based on subjective listening tests. It is to evaluate
synthesized speech in two aspects: its naturalness and similarity to real
speech from the target speaker.

##  4 Result and Analysis

###  4.1 Ablation Experiment on Loss Function

To verify the effectiveness of the tri-item loss function we proposed, we
compare it with different loss functions. The decline of loss functions are
shown in Fig. 2. We can see that the convergence speed is obviously
accelerated when the proposed tri-item loss function is used to train the
model. It shows that the proposed tri-item loss function is effective.

Fig. 2: Convergence rate of loss functions.

###  4.2 Quantitative Result

Recall that in the previous work [1, 2, 4, 5], a set of audio data are used to
train a model to obtain the personalized speech feature. We call this method
that synthesize personalized speech using speaker audio embeddings SYNTH-AUDIO
in this work. While the embedding vector of SYNTH-AUDIO is made by applying
the SE to the audio of the speaker, that of FR-PSS is generated by applying
the FE to the face images of the speaker. Since the FE was trained to minimize
the loss between the embedding vector from the SE and output vector from the
FE, SYNTH-AUDIO can be considered as the upper limit of this framework.

In Table 1, we calculate the differences between speech features extracted
from generated audio using different methods and the true speech feature ($\rm
T_{speech}$). We compare their distance by the $L_{1}$, $L_{2}$ and $Cos$. It
can be seen that the speech obtained by FR-PSS is close to the SYNTH-AUDIO. In
particular, adding gender prior knowledge can improve performance
significantly. For male priors, we only use male speakers for training and
testing, and for female priors we only use female speakers for training and
testing. Compared with neutral prior experiments, gender prior avoids gender
differences, so it gets smaller errors.

Besides, we compare the face features obtained by the FE and $\rm T_{speech}$
(see Table 2). Results show that by adding prior knowledge, the values of
$L_{1}$ and $L_{2}$ decrease dramatically, and the $Cos$ approaches to 1.

###  4.3 Qualitative Analysis

A visualization of speakers embedding is shown in Fig. 3 using the U-MAP [21].
We randomly select 10 speakers with 5 utterances per speaker. It can be seen
that speakers features are well separated in the speaker embedding space for
different speakers, either using the face feature or using the synthesized
speech feature by our FR-PSS. Besides, different utterances for the same
speaker are well clustered. This shows that the speech synthesized by our
model can well represent the personalized speech information.

Table 1: Performance of the proposed FR-PSS. $\rm FR-PSS$, $\rm FR-PSS_{n}$,
$\rm FR-PSS_{f}$ and $\rm FR-PSS_{m}$ means FR-PSS with no speech prior,
neutral prior, female prior and male prior, respectively. The difference
between them and $\rm T_{speech}$ are shown. $\downarrow$ represents the
smaller the better, and $\uparrow$ represents the larger the better.

Method |  $L_{1}\downarrow$ |  $L_{2}\downarrow$ |  $Cos\uparrow$
---|---|---|---
SYNTH-AUDIO |  6.251 |  0.664 |  0.887
$\rm FR-PSS$ |  8.388 |  0.865 |  0.869
$\rm FR-PSS_{n}$ |  7.769 |  0.805 |  0.836
$\rm FR-PSS_{f}$ |  6.963 |  0.785 |  0.881
$\rm FR-PSS_{m}$ |  7.129 |  0.809 |  0.892

Table 2: Difference between the face features generated by the FE and the true
speech features.

Method |  $L_{1}\downarrow$ |  $L_{2}\downarrow$ |  $Cos\uparrow$
---|---|---|---
$\rm FR-PSS$ |  9.579 |  0.896 |  0.847
$\rm FR-PSS_{n}$ |  5.920 |  0.567 |  0.910
$\rm FR-PSS_{f}$ |  5.462 |  0.509 |  0.921
$\rm FR-PSS_{m}$ |  5.613 |  0.516 |  0.943

Fig. 3: Visualization of speaker embeddings. (a): features of face image. (b):
features of synthesized speech by FR-PSS. The same color represents the same
person.

###  4.4 Subjective Evaluation

MOS is an assessment experiment based on subjective listening test, and it
includes two dimensions: naturalness and similarity. To verify the quality of
the speech synthesized by our proposed model, we invite 12 listeners to
participate in this evaluation. In the naturalness evaluation, each listener
rates the naturalness of 100 speech samples. In the similarity evaluation,
each listener is given 20 pairs of samples and is asked to score how similar
the synthesized speech is to the real one. All our MOS evaluations are aligned
to the absolute category rating scale [22], with rating scores from 1 to 5,
and the experimental results are shown in Table 3.

Table 3: MOS on subjective listening test.

Method |  Naturalness$\uparrow$ |  Similarity$\uparrow$
---|---|---
SYNTH-AUDIO |  3.83 |  2.43
FR-PSS(proposed) |  3.60 |  2.12
Face2Speech |  3.52 |  1.98

Since our work uses face information to synthesize personalized speech, the
MOS score is natural slightly lower than SYNTH-AUDIO which is the upper limit
of this framework. However, we extract speech features directly from face
images, and a good performance is achieved compared with the model that
extract speech features from speech to synthesize personalized audio. And in
terms of naturalness and similarity, our proposed method is better than
Face2Speech. Samples are available at https://github.com/hxs123hxs/FR-
PSS_example.

##  5 Conclusion

In this work, we innovatively propose the FR-PSS model to extract personalized
speech features from human faces and synthesize personalized speech using
neural vocoder. By designing three speech priors, a residual-guided strategy
is introduced to guide the face feature to approach the true speech feature as
much as possible. Experimental results show that our FR-PSS achieves a
satisfying performance compared with the method that synthesizes personalized
speech using a speech-derived embedding vector. In the future, we will
investigate a multi-task framework to further improve the efficiency of the
personalized speech synthesis.

##  6 Acknowledgements

This work was supported by the National Natural Science Foundation of
China(No.61977049), National Natural Science Foundation of China(No.62101351)
and the Tianjin Key Laboratory of Advanced Networking.

## References

  * [1] Yuxuan Wang, RJ Skerry-Ryan, Daisy Stanton, Yonghui Wu, Ron J Weiss, Navdeep Jaitly, Zongheng Yang, Ying Xiao, Zhifeng Chen, Samy Bengio, et al.,  “Tacotron: Towards end-to-end speech synthesis,”  Proc. Interspeech 2017, pp. 4006–4010, 2017.
  * [2] J. Shen, R. Pang, R. J. Weiss, M. Schuster, N. Jaitly, Z. Yang, Z. Chen, Y. Zhang, Y. Wang, R. Skerrv-Ryan, R. A. Saurous, Y. Agiomvrgiannakis, and Y. Wu,  “Natural tts synthesis by conditioning wavenet on mel spectrogram predictions,”  in proc. ICASSP, pp. 4779–4783, 2018.
  * [3] Li Liu, Thomas Hueber, Gang Feng, and Denis Beautemps,  “Visual recognition of continuous cued speech using a tandem cnn-hmm approach.,”  pp. 2643–2647, 2018.
  * [4] Ye Jia, Yu Zhang, Ron J Weiss, Quan Wang, Jonathan Shen, Fei Ren, Zhifeng Chen, Patrick Nguyen, Ruoming Pang, Ignacio Lopez Moreno, et al.,  “Transfer learning from speaker verification to multispeaker text-to-speech synthesis,”  pp. 4485–4495, 2018.
  * [5] Wei Ping, Kainan Peng, Andrew Gibiansky, Sercan O Arik, Ajay Kannan, Sharan Narang, Jonathan Raiman, and John Miller,  “Deep voice 3: 2000-speaker neural text-to-speech,”  in proc. ICLR, pp. 214–217, 2018.
  * [6] Tae-Hyun Oh, Tali Dekel, Changil Kim, Inbar Mosseri, William T. Freeman, Michael Rubinstein, and Wojciech Matusik,  “Speech2face: Learning the face behind a voice,”  in proc. CVPR, pp. 7539–7548, 2019.
  * [7] Jianrong Wang, Xiaosheng Hu, Li Liu, Wei Liu, Mei Yu, and Tianyi Xu,  “Attention-based residual speech portrait model for speech to face generation,”  arXiv preprint arXiv:2007.04536, 2020.
  * [8] Ran Yi, Zipeng Ye, Juyong Zhang, Hujun Bao, and Yong-Jin Liu,  “Audio-driven talking face video generation with learning-based personalized head pose,”  arXiv preprint arXiv:2002.10137, 2020.
  * [9] Shunsuke Goto, Kotaro Onishi, Yuki Saito, Kentaro Tachibana, and Koichiro Mori,  “Face2speech: Towards multi-speaker text-to-speech synthesis using an embedding vector predicted from a face image,”  in proc. Interspeech, pp. 1321–1325, 2020.
  * [10] Masanori Morise, Fumiya Yokomori, and Kenji Ozawa,  “World: a vocoder-based high-quality speech synthesis system for real-time applications,”  IEICE TRANSACTIONS on Information and Systems, vol. 99, no. 7, pp. 1877–1884, 2016.
  * [11] W. Li, W. Quan, A. Papir, and I. L. Moreno,  “Generalized end-to-end loss for speaker verification,”  in proc. ICASSP, pp. 4879–4883, 2018.
  * [12] Nal Kalchbrenner, Erich Elsen, Karen Simonyan, Seb Noury, Norman Casagrande, Edward Lockhart, Florian Stimberg, Aaron van den Oord, Sander Dieleman, and Koray Kavukcuoglu,  “Efficient neural audio synthesis,”  in proc. ICML, vol. 80, pp. 2410–2419, 2018.
  * [13] Sanghyun Woo, Jongchan Park, Joon-Young Lee, and In So Kweon,  “Cbam: Convolutional block attention module,”  in proc. ECCV, pp. 3–19, 2018.
  * [14] Jie Hu, Li Shen, and Gang Sun,  “Squeeze-and-excitation networks,”  in proc. PAMI, pp. 7132–7141, 2018.
  * [15] G. Levi and T. Hassncer,  “Age and gender classification using convolutional neural networks,”  in proc. CVPRW, pp. 34–42, 2015.
  * [16] E Eidinger, R Enbar, and T Hassner,  “Age and gender estimation of unfiltered faces,”  IEEE Transactions on Information Forensics and Security, vol. 9, no. 12, pp. 2170–2179, 2014.
  * [17] Qiong Cao, Li Shen, Weidi Xie, Omkar M Parkhi, and Andrew Zisserman,  “Vggface2: A dataset for recognising faces across pose and age,”  in 2018 13th IEEE international conference on automatic face & gesture recognition (FG 2018), 2018, pp. 67–74.
  * [18] Florian Schroff, Dmitry Kalenichenko, and James Philbin,  “Facenet: A unified embedding for face recognition and clustering,”  in proc. CVPR, pp. 815–823, 2015.
  * [19] Joon Son Chung, Arsha Nagrani, and Andrew Zisserman,  “Voxceleb2: Deep speaker recognition,”  Proc. Interspeech 2018, pp. 1086–1090, 2018.
  * [20] Heiga Zen, Viet Dang, Rob Clark, Yu Zhang, Ron J Weiss, Ye Jia, Zhifeng Chen, and Yonghui Wu,  “Libritts: A corpus derived from librispeech for text-to-speech,”  Proc. Interspeech 2019, pp. 1526–1530, 2019.
  * [21] L. Mcinnes and J. Healy,  “Umap: Uniform manifold approximation and projection for dimension reduction,”  The Journal of Open Source Software, vol. 3, no. 29, pp. 861, 2018\.
  * [22] ITUT Rec,  “P. 800: Methods for subjective determination of transmission quality,”  International Telecommunication Union, Geneva, vol. 22, 1996.


# An Overview of Minimum Convex Cover and Maximum Hidden Set

Reilly Browne

(January 2024)

###### Abstract

We give a review of results on the minimum convex cover and maximum hidden set
problems. In addition, we give some new results. First we show that it is NP-
hard to determine whether a polygon has the same convex cover number as its
hidden set number. We then give some important examples in which these
quantities don’t always coincide. Finally, We present some consequences of
insights from Browne, Kasthurirangan, Mitchell and Polishchuk [5] on other
classes of simple polygons.

##  1 Preliminaries

The minimum convex cover problem asks for the smallest cardinality set $B$ of
convex polygons whose union is equal to some target polygon $P$. We will refer
to the convex polygons as “convex pieces” so that the distinction between the
covering polygons and the target polygon is clear. The maximum hidden set
problem is the largest cardinality set $H$ of points within a target polygon
$P$ such that no two points $p,q\in H$ can see each other. Here, two points
$p,q$ see each other if and only if the line segment $pq$ is contained
entirely inside of the target polygon $P$.

Shermer[18] introduced the notion of a point visibility graph, an infinite
graph for which the vertices correspond to the points of a polygon and edges
exist between vertices if the corresponding points see each other. This lets
us redefine the minimum convex cover problem and the maximum hidden set
problem in terms of graph theory, namely with respect to the clique cover and
independent set problems

######  Definition 1.

[[18]] Given a polygon $P$, the point-visibility graph of P, $PVG(P)=(V,E)$
where $V=\\{p\;|\;p\in P\\}$ and $E=\\{(x,y)\;|\;\overline{xy}\subset P\\}$.

######  Definition 2.

For a polygon P, the hidden set number of P, hs(P), is the independence number
of PVG(P).

######  Definition 3.

For a polygon P, the convex cover number of P, cc(P), is the minimum number of
convex pieces needed to cover P. If $P$ is simple, then it is also the clique
covering number of PVG(P).

From these graph theory definitions, it becomes immediately obvious that the
following inequality holds:

$hs(P)\leq cc(P)$

This inequality holds for polygons with holes as well, where the graph
theoretical properties of convex cover do not hold up. It is not always the
case in polygons with holes that cliques in the PVG correspond to convex
pieces in the polygonal domain, specifically when the convex hull of the
points corresponding to the clique vertices contains a hole. This is important
for the correctness of Abrahamsen, Meyling, and Nusser’s [2] heuristic for
minimum convex cover in polygons with holes.

##  2 Hardness Results

For simple polygons, finding the minimum convex cover is known to be APX-hard
[11] i.e. there is no PTAS unless $P=NP$. This is also the case for maximum
hidden set [10]. In addition to hardness of approximation, minimum convex
cover has also been show to be $\exists\mathbb{R}$-hard by Abrahamsen [1].
When the problems are generalized to polygons with holes, we do not know any
additional hardness results for minimum convex cover, but maximum hidden set
becomes more difficult to approximate. Eidenbenz[10] shows that there unless
$P=NP$, then there exists an $\epsilon>0$ such that there is no polynomial
time approximation that achieves a better factor than $O(n^{\epsilon})$.

###  2.1 Determining the Gap

It is also NP-hard to determine the difference $cc(P)-hs(P)$. We define a
homestead polygon to be a polygon for which $cc(P)=hs(P)$. Therefore, it
suffices to show the decision problem of determining whether or not a polygon
is a homestead to be NP-hard.

The key component in the two NP-hardness reductions [18] [8] (both from 3-SAT,
the variant of the Boolean satisfiability problem where all clauses have 3
literals) for hidden set and convex cover in simple polygons is the
construction of a simple polygon which is a homestead if the 3-SAT instance is
satisfiable and a nonhomestead if it is not satisfiable.

######  Theorem 2.1.

Deciding if a simple polygon is a homestead polygon or not is NP-hard.

###### Proof.

It is sufficient to show that for any instance of 3-SAT, the corresponding
construction from Shermer’s [18] NP-hardness reduction for hidden set has
exactly the convex cover number $k$ which, if equal to the hidden set number,
indicates that the instance is satisfied. This is because we can simply apply
any algorithm for deciding if a polygon is a homestead polygon to this
construction in the same way that Shermer takes the value $k$ as input for a
maximum hidden set decision algorithm. The full details of the construction
are provided in Shermer’s paper.

For a 3-SAT instance with m clauses and n variables, $k=2mn+8n+m+1$. We show
that there is a subgraph of every construction that has clique cover number
equal to $K$. Shermer shows a set of convex pieces which cover the
construction of size $k$, so we just need to prove that no cover with less
pieces can exist using the subgraph argument. First we show the subgraph in
Figure 1, with dotted edges signifying that the edge connects to a point in a
different component. We use the same labels as in Shermer’s proof.

Figure 1: The subgraphs in each of the shermer construction components. Top is
a literal unit, left is a consistency checker, right is a clause unit and
bottom is the overall structure, indicating we are including the corners.

Just as in the previous examples, we start by finding a large clique in the
complement graph since the chromatic number of the complement must be at least
the size of that clique. A clique in the complement graph is an independent
set in the graph, so we will select a set of points identified in Figure 7
such that no two share an edge.

For each literal unit, we take all the $e$ points and the $P_{i,2}$ points for
$0\leq i\leq n$, amounting to $2mn+4n$ points. For each consistency checker,
we take all the $f$ for an additional $2n$ points. For each clause checker, we
take all the $q_{0}$ points for an additional $m$ points. And from the overall
box structure, we take $c_{1}$. The total size of this clique is $2mn+6n+m+1$,
meaning we will have to show that an additional $2n$ colors are needed to
color the complement graph.

For a start, we can label $c_{2},c_{3},c_{4}$ the same color as $c_{1}$
without any issue. For each $P_{i,5}$ in each literal unit, we can label
$P_{i,5}$ with the same color. For each clause unit, $q_{2},q_{3}$, can be
labeled with the same color as the $q_{1}$. This leaves only the $f_{1},f_{5}$
from each literal unit uncolored. The $f_{1}$ can be colored the same as the
$P_{0,2}$ (or $P_{0,5}$ if its a bottom clause unit), but if we colored
$P_{0,5}$ ($P_{0,2}$ for bottom) the same as $P_{0,2}$ ($P_{0,5}$ for bottom),
then we can’t. The same applies for $f_{5}$, but with the complement literal
units (CLUs). However, $f_{1}$ and $f_{5}$ can be colored with the same color.
Therefore we need only an additional $2n$ colors to color $f_{1}$ and $f_{5}$.
Therefore, the chromatic number of the complement of the subgraph is
$2mn+6n+m+1=k$

Since the chromatic number of the complement of an induced subgraph of the PVG
of the construction is equal to $k$, this means that the convex cover of the
construction must be at least $k$. Since Shermer shows such a cover, this
implies that the convex cover number of the construction is exactly $k$.

Since the convex cover number of the Shermer construction $I^{\prime}$ for any
3-SAT instance $I$ is equal to $k$, and the hidden set number of $I^{\prime}$
is strictly less than $k$ if and only if $I$ is unsatisfiable, 3-SAT reduces
to deciding if a simple polygon is a homestead polygon or not. Thus, since
3-SAT is NP-hard, deciding if a simple polygon is a homestead polygon or not
must also be NP-hard.

∎

######  Corollary 2.2.

Deciding if a polygon with or without holes is a homestead polygon or not is
NP-hard.

###### Proof.

Since deciding if a simple polygon is a homestead polygon is NP-hard, this
naturally implies that the more general case of a polygon with or without
holes is also NP-hard. ∎

In addition to these hardness proofs, we present several simple polygons for
which $hs(P)<cc(P)$. The first polygon for which it was proven that the hidden
set number and convex cover number do not coincide was given in Browne and
Chiu [7]. The polygons we present each have different properties, some of
which will be exploited later for approximation algorithms. However, exact
algorithms which find a convex cover and hidden set of the same size cannot
exist for these subclasses since they are not universally homesteads, meaning
that alternative methods would have to be used for both problems than those of
the type presented here.

######  Theorem 2.3.

There exists an orthogonal polygon which is not a homestead polygon

###### Proof.

Figure 2: Orthogonal and x-monotone polygon, $M$ which is not a homestead
polygon.

Observe the example $M$ in Figure 2. This polygon is clearly orthogonal. First
we will show that $M$ does not admit a hidden set larger than size 3 and then
show that the minimum convex cover must be greater than or equal to $4$ by
using a theorem from graph theory.

We start by finding a convex cover of size 4. We can remove out the points
that are in the intersection of 2 or more convex pieces since their use can
only admit a hidden set of size 3 or smaller. This is because if among the two
remaining convex pieces, there can only be an additional two points that can
be hidden in them, by definition of convexity. See Figure 3, the regions
outlined in purple are the remaining points that have not been eliminated.

Figure 3: Showing the remaining regions of $M$ that haven’t been ruled out by
a starting convex cover.

Now we show that for each purple region $R_{i}$, after taking out the strong
visibility region of $R_{i}$, the rest of $M$ can be covered with just 2
convex pieces. By definition of strong visibility, all the points in $R_{i}$
see all the points in the strong visibility region. Therefore, using any point
in $R_{i}$ disqualifies usage of the strong visibility region, hence covering
the rest with 2 convex pieces means at most 2 additional hidden points can be
used.

For some of the purple regions, we split $R_{i}$ into 2 regions and analyze
them separately because the strong visibility region of the whole of $R_{i}$
is just a convex piece and thus we needed 3 to complete that cover, but when
the region is split both pieces can have the remaining portion covered with
just 2. This full analysis is shown in Figure 4, with the specific region
being analyzed in each iteration shaded in purple.

Figure 4: Showing the size 2 convex covers of the remaining region after
taking out the strong visibility regions of the purple regions.

Since, as is shown in Figure 4, including the strongly visible region of any
purple region allows the rest of $M$ to be covered with just 2 added convex
pieces, we know that $M$ admits hidden sets of size at most 3.

For convex cover, we find an indueced subgraph of the PVG of $M$ with clique
cover number 4. From Gella and Artes [13], we know that for graph $G$ and
induced subgraph $H$, the following inequality holds:

$cc(G)\geq cc(H)$ (1)

Therefore, since convex cover is simply the clique cover of the point
visibility graph, finding that clique cover number of the point visbility
graph in $M$ restricted to a small set of points is 4 will suffice to show
that $cc(M)\geq 4$.

We show this through finding the chromatic number of an isomorphism of the
complement graph in Figure 5. Start by observing that nodes 1,2,3 form a
clique in the complement, thus must all have different colors, say red, blue
and green respectively. Node 6 is adjacent to both red (1) and blue (2), it
must be green. Node 5 is adjacent to green (6) and red (1) and thus must be
blue. Node 7 is adjacent to green (3) and blue (5) so it must be red. Since 4
is adjacent to green (3), red (7), and blue (5), it must be a fourth color.
Therefore the chromatic number of $G^{\prime}$ must be 4. This in turn proves
that $cc(G)=4$ and in turn $cc(P)\geq 4$. Therefore $M$, an orthogonal
polygon, is not a homestead.

Figure 5: Showing an induced subgraph of $PVG(M)$ with $cc(G)=4$ from
chromatic number of compliment.

∎

######  Corollary 2.4.

There exists an x-monotone polygon which is not a homestead polygon.

###### Proof.

The polygon $M$ is also clearly x-monotone in addition to being orthogonal.
Therefore, this corollary is true from the previous proof that $M$ is not a
homestead. ∎

####  2.1.1 General position

Another subclass of polygon that we had conjectured was comprised only of
homestead polygons was polygons whose vertices were in general position. A set
of vertices is said to be in general position if no 3 vertices are collinear
and no 4 vertices are said to be cocircular.

Figure 6: A polygon $W$ which has no three collinear vertices and is not a
homestead.

######  Theorem 2.5.

There exists a polygon which is not a homestead polygon which has vertices in
general position

###### Proof.

First we show a polygon $W$ (in Figure 6 which is a polygon where no 3 of the
vertices are collinear, but does have cocircular points, and is not a
homestead polygon. The polygon exhibits rotational symmetry which allows us to
simplify our analysis. First we show that the hidden set number of $W$ is 2,
then that its convex cover number is 3 and then give a modification of
$W^{\prime}$ that does not change any of the properties which make $W$ not a
homestead.

For hidden set, we analyze the green region of $W$ as, due to rotational
symmetry, it is equivalent to analyzing all the other regions. Each of the
colored regions have nodes in their centers. These nodes are connected if
their regions are strongly visible to each other (their strong visibility
regions contain all of the other). Any point in the green region sees all the
points in the red and orange regions, meaning we need to cover the blue and
purple regions with just one convex polygon. Since blue and purple have an
edge, this implies that they see each other, so simply taking their convex
hull will produce the convex piece. Because only 1 additional convex piece is
needed after using the strong visibility region of the green region, and the
green region is, by rotational symmetry, equivalent to all the other regions
which total all of $W$, $W$ admits hidden sets of size at most 2.

For convex cover, we take the convex vertices as our subgraph (”points of the
star”). It is clear that the graph induced by these vertices is the same as
that of the regions from the hidden set discussion, ie the convex vertex in
the green region sees the vertices in the red and orange regions but not the
blue and purple. This graph is $C_{5}$, a well known graph which has clique
cover number 3.

Figure 7: A polygon $W^{\prime}$ whose vertices are in general position and
which is not a homestead polygon.

Observing $W^{\prime}$ (see Figure 7), it is clear that the colored regions
are related just as those of $W$. The convex vertices also are related in the
same way as those of $W$. Therefore, $W^{\prime}$, a polygon which has
vertices in general position, must have hidden set number of at most 2 and
convex convex number of at least 3 and must not be a homestead polygon.

∎

######  Corollary 2.6.

There exists a star-shaped polygon which is not a homestead polygon.

###### Proof.

A star shaped polygon is a polygon for which there is some point or set of
points that see the entirety of the polygon. The center point of $W$ is in all
of the colored regions, therefore must see the entirety of $W$. Therefore,
since $W$ is not a homestead polygon, we know that it is not the case that the
entire class of star-shaped polygons are homestead polygons. ∎

##  3 Exact and Approximation Algorithms

###  3.1 Polygons with Holes

For polygons with holes, there is no known approximation algorithm for hidden
set which performs better than simply placing a single point inside the
polygon, which gives a $O(1/n)$ approximation. However, there does exist a
$O(\log n)$-approximation which runs in $O(n^{29}\log n)$ time from Eidenbenz
and Widmayer [11]. Their algorithm starts by showing that a factor of at most
3 is lost by restricting the polygons to unions of cells in a polynomial sized
arrangement. Then, they provide a set of maximal convex pieces from which the
optimal convex cover restricted to that arrangement must use. From there, the
set of maximal convex pieces can be treated as sets and the cells of the
arrangement as elements for a set cover. This permits the use of the greedy
set cover algorithm on this set of maximal convex pieces, yielding a $O(\log
n)$ approximation for the restricted problem, which in turn is only a constant
factor away from the actual optimal. In order to make sure this runs in
polynomial time, a dynamic program is used to find the greedy choices of
convex pieces, since the set of maximal convex pieces is superpolynomial.

If the number of holes is $o(\log n)$, then a better approximation for minimum
convex cover can be found using the constant factor approximation for the
simple case given by Browne, Kasthurirangan, Mitchell, and Polishchuk [5].
Simply decompose the polygon with holes into $h+1$ simple polygons by using
horizontal chords from the holes to the boundary. This will decompose the
polygon into at worst $h+1$ pieces. Applying the algorithm for simple polygons
to each of these pieces yields a $6h+6$-approximation. With slightly more care
with respect to the chords, a similar approximation for maximum hidden set can
be achieved, specifically making sure that no

###  3.2 Simple Polygons

Browne, Kasthurirangan, Mitchell, and Polishchuk [5] gave an argument that by
losing only a constant approximation factor (3 for convex cover and 1/4 for
hidden set) we can reduce the problem in simple polygons to that of just
considering the case of polygons that are weakly visible from a convex edge,
which are defined in Section 3.3. They achieve this using a window partition
algorithm from Suri [19], which decomposes a simple polygon into regions by
their link distance from a point. See Figure 8 for an example of this
decomposition When this point is a convex vertex of the polygon, these regions
are all polygons weakly visible from a convex edge.

Figure 8: Top: Window partition of a simple polygon given in stages (Figure 3
from [17]): The windows are yellow. Bottom: Right (red) and left (blue)
windows of the weak visibility polygon (gray) of the yellow window. (Figure 6
from [5])

For convex cover, they argue that no convex body can intersect more than 3
different regions. This means that by restricting convex pieces to stay within
one region, only an additional factor of 3 is lost. Using their approximation
for convex cover in polygons weakly visible from a convex edge gives a
2-approximation for the convex cover of each region. Taking the union of these
covers gives a cover of the whole polygon which is at worst 6 times as bad as
the optimal solution.

For hidden set, they use an argument from Alegría, Bhattacharya and Ghosh [3]
that partitions the set of regions into 4 subsets. They define the subset
membership by the link distance modulo 2 and the type of turn which was made
from the last window to the window illuminating this region, i.e. a left turn
or a right turn. We give their figure for distinguishing between left and
right windows in Figure 8. These 4 subsets are each visually independent sets
of regions, meaning that if you take all the regions within a subset, two
points can only see each other if they are in the same region. Therefore, if
we have hidden sets in each region, for each subset we can take the union of
the hidden sets for its members since the regions are visually independent of
each other. If we take the largest of these 4 hidden sets, then that would
give a 1/4 approximation. However, their algorithm gives a 1/2 approximation
for the case of polygons weakly visible from a convex edge, so these factors
multiply to 1/8.

###  3.3 Polygons Weakly Visible from a Convex Edge

Browne, Kasthurirangan, Mitchell, and Polishchuk [5] give a 2-approximation
for minimum convex cover and a 1/2 approximation for maximum hidden set. They
do so by finding a hidden set and a convex cover such that the convex cover is
at most 2 times the size of the hidden set, which implies those factors due to
the inequality from Shermer [18], $hs(P)\leq cc(P)$. Their base algorithms for
both problems run in $O(n^{2+o(1)})$ time, based on recent results on maximum
flow [4]. However, they remark that the runtime can be decreased to $O(n^{2})$
for maximum hidden set, the details of which we present here in Section 3.3.2.

####  3.3.1 Using Edges as a Poset

The key insight of Browne, Kasthurirangan, Mitchell, and Polishchuk [5] is
that we can treat the edges of a polygon weakly visible from a convex edge as
a partially ordered set (poset). This poset is determined by strong
visibility, i.e. whether all of the points in an edge $e_{i}$ see all of the
points in a edge $e_{j}$, and then if strong visibility exists the elements
are comparable, with the comparison being the counterclockwise order of the
edges. This can also be thought of as a DAG, where there is an arc pointed
towards the later of the two edges. Importantly, this relation is transitive,
so if for $i<j<k$, $e_{i}$ strongly sees $e_{j}$ and $e_{j}$ strongly sees
$e_{k}$, then $e_{i}$ strongly sees $e_{k}$.

Figure 9: Figure 1 from [5]. Arcs indicating the partial ordering of selected
edges.

Using this poset, we can find a set of edges for which no pair strongly see
each other, also called an antichain. These edges may share partial
visibility, so we need to pick special points along each edge so that they
form a hidden set. Specifically, they choose points that are sufficiently
close to one of the two endpoints of the edge based on a variation of the
visbility decomposition of the polygon. From there, it suffices to simply
choose the correct endpoint to be near for each edge, which is done using a
recursive procedure on the edges. We give an alternate set of these candidates
in Section 3.3.2.

For convex cover, they start by considering the minimum path cover of the
poset. From this path cover, they construct a set of convex pieces which
partially cover the polygon. From there, they augment the convex pieces to
include some additional area. After this augmentation, they add an additional
convex piece for every one of the original pieces, doubling the number of
pieces. These additional convex pieces prove to be sufficient to complete the
cover.

Due to Dilworth’s [9] theorem, the maximum antichain and the minimum path
cover of a poset are of the same size. This means there are at most twice as
many convex pieces as hidden points, demonstrating their factors of 2 and 1/2
respectively. Due to recent advances in the maximum flow problem [4], finding
either the maximum antichain or the minimum path cover both take
$O(n^{2+o(1)})$ deterministically.

####  3.3.2 A hidden set without an antichain

We give the details of the improved algorithm for the maximum hidden set which
runs in $O(n^{2})$ mentioned in Browne, Kasthurirangan, Mitchell and
Polishchuk [5].

######  Lemma 3.1.

There exists a set $S\subset\partial P$ of $2n-2$ points such that for any
antichain $I$ in $G$, there is a hidden subset of points $H\subset S$ with
$|H|=|I|$. Such a set $S$ can be computed in polynomial time.

###### Proof.

First we describe how to obtain the set $S$, and then prove its properties.
For each edge $e_{i}$, $i=1,2,\ldots,n-1$, we find two points $s_{i}\in e_{i}$
(near $v_{i}$) and $t_{i}\in e_{i}$ (near $v_{i+1}$); these $2n-2$ points
constitute the set $S$.

We compute the shortest path trees, $SPT(v_{i})$, for each vertex $v_{i}$;
this takes $O(n)$ time per vertex [15], so overall time $O(n^{2})$. This
allows us to access the parent of $v_{j}$ with respect to $SPT(v_{i})$ in
$O(1)$.

This in turn allows us to determine whether the $SP(v_{i},v_{j})$ contains no
vertex (besides $v_{i},v_{j}$), or $\geq 1$ vertices in $O(1)$ time. We can
use this to calculate $s_{i}$ and $t_{i}$ ie. how close each must be to
$v_{i}$ and $v_{i+1}$, respectively. Each edge pair $e_{i},e_{j}$ defines 2
constraints, one on either $s_{i}$ or $t_{i}$ and one on either $s_{j}$ or
$t_{j}$. We find these 2 constraints simultaneously. Assume without loss of
generality, that $i<j$. This assumption allows us to know that we are
constraining $t_{i}$ and $s_{j}$ and to consider $SP(v_{i+1},v_{j})$. There
are 2 cases depending on the complexity of $SP(v_{i+1},v_{j})$.

  1. Case (1)

$SP(v_{i+1},v_{j})$ is a line segment. If this is the case, then we will
consider the extensions of both $e_{i}$ and $e_{j}$. If the extension of
$e_{j}$ intersects the edge $e_{i}$ at a point $p_{i}$, then $t_{i}$ must be
strictly closer to $v_{i+1u}$ than $p_{i}$ is to $v_{i+1}$. If the extension
of $e_{i}$ intersects the edge $e_{j}$ at a point $p_{j}$, then $s_{j}$ must
be strictly closer to $v_{j}$ than $p_{j}$ is to $v_{j}$. Otherwise, there is
no constraint made. See the left image in Figure 10.

  2. Case (2)

$SP(v_{i+1},v_{j})$ contains at least one vertex (other than $v_{i+1},v_{j}$).
Let us call this vertex $u$. Consider the line parallel to
$\overleftrightarrow{v_{i+1}v_{j}}$ that passes through $u$. If this line
intersects the edge $e_{i}$ at a point $p_{i}$, then $t_{i}$ must be strictly
closer to $v_{i+1}$ than $p$ is to $v_{i+1}$. If this line intersects the edge
$e_{j}$ then $s_{j}$ must be strictly closer to $v_{j}$ than $p_{j}$ is to
$v_{j}$. Otherwise, there is no constraint made. See the right image in Figure
10.

Figure 10: Cases for placements of $s_{i}$ and $t_{j}$ for edges
$e_{i}=v_{i}v_{i+1}$ and $e_{j}=v_{j}v_{j+1}$ in $P$. Left: Case (1), right:
Case (2). In considering the hidden subset: $i=i_{1},j=i_{|I|}$.

After completing all these pairwise comparisons, we take the most restrictive
constraint for each $s_{i}$ (closest to $v_{i+1}$) and $t_{i}$ (closest to
$v_{i}$). Set the point to halfway between this constraint and the respective
vertex (or the midpoint of the edge if there is no constraint). Each
constraint takes $O(1)$ to compute since we can use the SPT parent of either
as the one vertex in Case (2). There are $\leq n$ constraints per point
($s_{i}$ and $t_{i}$), which means it takes a total of $O(n^{2})$ time to
compute $S$.

Now we show that such a set $S$ admits a hidden subset $H$ for every antichain
$I$ such that $|H|=|I|$. Particularly, there are three conditions (a),(b),(c)
such that there is at least one $H$ that satisfies both (a),(b) and one $H$
which satisfies both (a),(c). These can be the same subset satisfying all
three. (a) For each edge $e_{i}\in L$, $H$ admits either $s_{i}$ or $t_{i}$.
(b) The edge of lowest index $e_{i_{1}}$ admits $t_{i_{1}}$ into $H$, and (c)
The edge with the highest index $e_{i_{|I|}}$ admits $s_{i_{|I|}}$ into $H$.

We can show this by induction on $|I|$. If $|I|=1$, then
$e_{i_{1}}=e_{i_{|I|}}$. Therefore, to satisfy (a)(b) we use
$\\{t_{i_{1}}\\}$. To satisfy (a)(c) we use
$\\{s_{i_{|I|}}\\}=\\{s_{i_{1}}\\}$. Since the base case holds, we then show
that if this holds for $|I|\in[1,m-1]$, then it also holds for $|I|=m$.

For $|I|=m$, we have the same 2 cases as in the construction of $S$, but here
we work with $e_{i_{1}}$ and $e_{i_{|I|}}$ instead of $e_{i}$ and $e_{j}$.
Refer to Fig. 10 for a visual of the cases.

  1. Case (1)

$SP(v_{i_{1}+1},v_{i_{|I|}})$ is a line segment. Therefore $v_{i_{1}+1}$ sees
$v_{i_{|I|}}$. For $e_{i_{1}},e_{i_{|I|}}$ to not have an arc in $G$, either
$v_{i_{1}}$ or $v_{i_{|I|+1}}$ lies above the line
$\overleftrightarrow{v_{i_{1}+1},v_{i_{|I|}}}$. Otherwise, by chord property
they would see each other. If this is the case, then the only way that
$t_{i_{1}}$ could see $s_{i_{|I|}}$ is if one of these lies below the edge
extension of whichever lies above $v_{i_{1}+1},v_{i_{|I|}}$, which we know is
not the case from the constraints given in the construction above. See the
left image of Fig. 10. Since one must lie above the line
$\overleftrightarrow{v_{i_{1}+1},v_{i_{|I|}}}$, either one or neither can see
into the line segment $v_{i_{1}+1},v_{i_{|I|}}$.

Consider the case where $t_{i_{1}}$ sees into ${v_{i_{1}+1},v_{i_{|I|}}}$.
From the inductive assumption, we know there is a subset $H_{i_{1}}$
corresponding to $I_{i_{1}}=I\setminus e_{i_{|I|}}$ that satisfies (a),(b).
Since $e_{i_{1}}$ has a lower index than all other edges in $I_{i_{1}}$, we
know that $t_{i_{1}}$ is admitted into $H_{i_{1}}$. Since $s_{i_{|I|}}$ cannot
see into ${v_{i_{1}+1},v_{i_{|I|}}}$, it cannot see any other edge in
$I_{i_{1}}$. Because $s_{i_{|I|}}$ has a higher index than all edges in
$I_{i_{1}}$, $H_{i_{1}}\cup s_{i_{|I|}}$ forms a hidden subset of size $|I|=m$
that satisfies all three of (a),(b),(c). If instead $s_{i_{|I|}}$ sees into
${v_{i_{1}+1},v_{i_{|I|}}}$ or neither do, the argument is identical, except
that $H_{i_{|I|}}$ from $I_{i_{|I|}}=I\setminus e_{i_{1}}$ will satisfy
(a),(c) and then the union $H=H_{i_{|I|}}\cup\\{t_{i_{1}}\\}$ will satisfy
(a),(b),(c).

  2. Case (2)

$SP(v_{i_{1}+1},v_{i_{|I|}})$ contains at least one vertex (other than
$v_{i_{1}+1},v_{i_{|I|}}$). From the comparison between $e_{i_{1}}$ and
$e_{i_{|I|}}$, we know that both $t_{i_{1}},s_{i_{|I|}}$ lie to the left of
the directed line parallel to $\overleftrightarrow{v_{i_{1}},v_{i_{|I|}}}$
through some vertex $u$ of $SP(v_{i_{1}+1},v_{i_{|I|}})$. This is because
$SP(v_{i_{1}+1},v_{i_{|I|}})$ makes only left turns [14, Lemma 2], meaning $u$
must lie to the right of directed line
$\overleftrightarrow{v_{i_{1}},v_{i_{|I|}}}$. $t_{i_{1}}$ and $s_{i_{|I|}}$
must both lie between these two lines. This further means no point in the
interval $[t_{i_{1}},u)$ can see any point in the interval $(u,s_{i_{|I|}}]$,
as this would violate the simplicity of the polygon. See the right image of
Fig. 10.

This allows us to consider all the edges of $I$ in interval $[t_{i_{1}},u)$,
which we denote as $I_{i_{1}}$, and all the edges of $I$ in the interval
$[u,s_{i_{|I|}})$, which we denote as $I_{i_{|I|}}$. We know a hidden subset
$H_{i_{1}}$ abiding by (a),(b) exists for $I_{i_{1}}$ and a hidden subset
$H_{i_{|I|}}$ abiding by (a),(c) exists for $I_{i_{|I|}}$. Because no point in
one interval sees any point in the other, $H_{i_{1}}\cup H_{i_{|I|}}$ must be
a hidden subset of size $|I|=m$, abiding by all three (a),(b),(c).

Therefore, since in all cases we can obtain a hidden subset $H$ of $S$ such
that $|H|=|I|$, we know, by induction, that Lemma 3.1 holds. We also know that
such a set $S$ can be calculated in $O(n^{2})$ time. ∎

######  Theorem 3.2.

For a weakly visible polygon $P$, a hidden set of size greater than or equal
to the size of the largest antichain in $G$ can be found in polynomial time.

###### Proof.

From Lemma 3.1, we know that there exists a set of points $S$ of size $2n-2$
where for any antichain we can take a subset of $S$ as a hidden set of the
same size as the antichain. This means that for the largest antichain, there
exists a hidden subset of $S$ of the same size.

Because the set of points $S$ are on the boundary on $P$, this means that we
can define a degenerate polygon $P^{\prime}$ with $3n-2$ vertices that
includes the points $S$ as additional vertices to those in $P$. We include
these points by simply splitting the edges that they lie on, changing nothing
about the actual geometry of $P$. Because none of the points in $S$ are along
$W$, $P^{\prime}$ remains a weakly visible polygon. We can apply the
$O(n^{2})$ dynamic programming (DP) algorithm from [14] to find a maximum
hidden vertex set among these points. To be specific, we will exclude the
vertices $v_{1}$ and $v_{n}$ from consideration in placing hidden vertices.
Excluding the vertices of $W$ is important for extending this to arbitrary
simple polygons. Because the DP on $P^{\prime}$ considers all points in $S$,
this hidden vertex set must be at least as large as the hidden subset of $S$
corresponding to the largest antichain.

The total runtime of this reduces to simply finding $S$ and then applying the
algorithm from [14], both of which are $O(n^{2})$. From earlier, we know that
a hidden set that is the same size as the largest antichain of the edges is a
1/2-approximation for the maximum hidden set, so this provides a faster
approach to finding an approximate maximum hidden set for weakly visible
polygons and simple polygons in general by extension. ∎

###  3.4 Convex cover and hidden set in convex fans and monotone mountains

A convex fan is a polygon $P$ which contains a convex vertex $v$ where for all
points $p\in P$, $v$ sees $p$. Here, convex vertices can also include straight
vertices, those with angle measure exactly 180∘.

######  Theorem 3.3.

For any convex fan $P$ with $n$ vertices, a maximum hidden set and a minimum
convex cover of $P$ can be found in $O(n^{2+o(1)})$ time.

###### Proof.

We know that for either edge incident on $v$, this edge must be convex.
Otherwise, $v$ would not see the points on the boundary after the reflex
vertex, which contradicts the definition of a convex fan. This means that $P$
is weakly visible from a convex edge ($e_{i}$), and the edges of $P$ admit a
partial ordering from the strong visibility relation from Browne,
Kasthurirangan, Mitchell, and Polishchuk (see Section 3.3).

Since each edge $e_{i}$ in $P$ strongly sees $v$, it must be the case that the
$CH(e_{i}\bigcup v)\subset P$, where $CH$ indicates the convex hull. We can
produce a decomposition of $P$ using these convex pieces. It also is the case
that every set of edges that strongly see each other will also strongly see
$v$, which means that for every chain in the poset, we can construct a convex
piece that includes $v$. These convex pieces are a superset of the pieces in
the decomposition corresponding to the edges in the chain, which means that
they form a complete convex cover. This convex cover is equivalent to the size
of the hidden set found from the anti-chain using the approach from Browne,
Kasthurirangan, Mitchell, and Polishchuk (see Section 3.3). We give an example
of such a set and convex cover in the right subfigure of Figure 11. This
procedure takes time equivalent to the case of weakly visible polygons,
$O(n^{2+o(1)})$. ∎

Figure 11: Showing optimal hidden sets and convex covers for a monotone
mountain (Left) and a convex fan (Right)

Monotone mountains are simple polygons composed of an $x$-monotone chain and a
single edge $W$ formed by the vertex with the lowest $x$-coordinate and the
vertex with the highest $x$-coordinate. An $x$-monotone chain is a polygonal
chain composed of vertices whose $x$-coordinates are non-decreasing.

######  Theorem 3.4.

For any monotone mountain $P$ with $n$ vertices, a maximum hidden set and a
minimum convex cover of $P$ can be found in $O(n^{2+o(1)})$ time.

###### Proof.

A similar argument as in Theorem 3.3 can be made for the case of monotone
mountains.

Since the opposite chain ($W$) of the $x$-monotone chain is simply an edge,
every point along the boundary sees the corresponding point on $W$ with the
same $x$-coordinate, since a piece of boundary would have to violate
$x$-monotonicity to block this vision. This means that $W$ is a convex edge
which weakly sees the entirety of $P$.

It is also the case that if an edge $e_{i}$ strongly sees another edge
$e_{j}$, $e_{i}$ must also strongly see the corresponding points to $e_{j}$
along $W$. This follows from the $x$-monotocity as well as the chord property
[14][Lemma 1]. By the chord property, we know that no piece of boundary
between the edges in clockwise order blocks $e_{i}$ from seeing the
corresponding points of $e_{j}$ along $W$. Therefore, either a piece of
boundary from before $e_{i}$ must block it or a piece of boundary after
$e_{j}$, which would violate $x$-monotonicity.

Since the strong visibility relation between two edges also applies to the
regions below these edges down to the corresponding points in $W$, this allows
us to decompose the polygon into these vertical ”slabs”, just like with convex
fans. The union of these slabs is equal to $P$. Therefore, we can again use
the chain cover of the edges to obtain a set of convex pieces that will now
cover the entirety of $P$. The hidden set algorithm remains exactly the same.
Therefore, since we have a hidden set and convex cover of the same size, these
must both be optimal. This procedure takes time equivalent to the case of
weakly visible polygons, $O(n^{2+o(1)})$. We give an example convex cover and
hidden set in Figure 11. ∎

###  3.5 Rocking chair polygons

We give a generalization of monotone mountains which we refer to as rocking
chair polygons. We define a rocking chair polygon $P$ as a polygon composed of
a $x$-monotone chain $v_{1},v_{2},...v_{t}$ and a convex chain
$v_{t},v_{t+1},...v_{1}$. Without loss of generality, we can consider $v_{1}$
to be the point with the lowest $x$-coordinate and $v_{t}$ to be the point
with the highest $x$-coordinate and that the vertices are in clockwise order.

######  Theorem 3.5.

For any rocking chair polygon $P$, a maximum hidden set and a minimum convex
cover of $P$ can be found in $O(n^{2+o(1)})$ time.

###### Proof.

This is simply a generalization of Theorem 3.4. Consider the point with the
lowest $y$-coordinate, $v_{min}$. We can draw a horizontal line through
$v_{min}$ and consider the monotone mountain formed by extending vertical
segments down from $v_{1}$ and $v_{t}$ onto this horizontal. This forms a
monotone mountain $P^{\prime}$. This monotone mountain can be covered with
convex pieces using the algorithm from Theorem 3.4 and have hidden points
placed similarly. Specifically, we will place the points on the x-monotone
chain, so exclude the two vertical segments from consideration. Since the
monotone mountain coverage algorithm from Theorem 3.4 clearly covers these
vertical segments, we will still have a cover of $P^{\prime}$ and a hidden set
of the same size. While the hidden points of $P^{\prime}$ are also hidden
points in $P$, the convex pieces will not necessarily be constrained to $P$,
such as in Figure 12. However, due to the convexity of the convex chain, if we
consider $C=C^{\prime}\cap P$ for every convex piece $C^{\prime}$ of the
convex cover of $P^{\prime}$, all pieces $C$ will be convex. Since $P\subset
P^{\prime}$, $\bigcup_{C^{\prime}\in cc(P^{\prime})}(C\cap P)=P$.

Figure 12: A convex cover and a hidden set in a rocking chair polygon (green
and red) and the superimposed monotone mountain (grey)

∎

###  3.6 Convex cover and hidden set in star-shaped polygons

A star shaped polygon is one which has a nonempty kernel. The kernel of a
polygon $P$ is the set of points $K$ for which every point $p\in P$ sees all
points in $K$.

######  Theorem 3.6.

A 2-approximate convex cover and a 1/2-approximate hidden set in a star-shaped
polygon can be found in polynomial time.

###### Proof.

We can use the results from Theorem 3.3 to accomplish this. The kernel of a
star shaped polygon can be found in $O(n)$ time [16], thus allowing us to find
a point $p$ in $P$ which sees every other point in $P$. We can consider an
arbitary convex vertex $v$ of $P$ and extend the line segment $vp$ until it
forms a chord of $P$. This chord partitions $P$ into two (degenerate) convex
fans. We can use the algorithm from Theorem 3.3 on both of these, which runs
in $O(n^{2+o(1)})$ time. We take the larger of the two hidden sets and the
union of the convex pieces, which yield a 2-approximation for convex cover and
a 1/2 approximation for hidden set. ∎

###  3.7 Convex cover and hidden set in weak visibility polygons

A weak visibility polygon is a polygon $P$ for which a chord of $P$ weakly
sees all of $P$. This is a relaxation of the requirements for a weakly visible
polygon.

######  Theorem 3.7.

A 4-approximate convex cover and a 1/4-approximate hidden set in a weak
visibility polygon can be found in polynomial time.

###### Proof.

This can be done nearly identical to Theorem 3.6. Ghosh et al. [14] provide an
algorithm that finds a chord which sees all of $P$ (if it exists) that runs in
$O(n^{2})$ time. This allows us to split $P$ into two subpolygons that are
weakly visible polygons. This means we can apply the algorithm from Browne,
Kasthurirangan, Mitchell, and Polishchuk[5] to achieve a 4-approximation (and
a 1/4 approximation), again taking the better of the two hidden sets (1/2
approximate) and all the convex pieces. ∎

###  3.8 Convex cover and hidden set in simple orthogonal polygons

Simple orthogonal polygons are simple polygons for which all angles are either
$90^{\circ}$ or $270^{\circ}$. We give a 2-approximation for convex cover and
a 1/2-approximation for hidden set.

######  Theorem 3.8.

A 2-approximate convex cover and a 1/2-approximate hidden set in a simple
orthogonal polygon can be found in polynomial time.

###### Proof.

Franzblau [12] gave an $O(n\log n)$ algorithm which finds a 2-approximation
for finding a minimum number of axis-aligned rectangles to cover a simple
orthogonal polygon. Since axis-aligned rectangles are convex, this also yields
a convex cover. This algorithm begins by extending all horizontal edges to
form a partition of the polygon into axis-parallel rectangles. Although
unnecessary for improving the 2-factor, the algorithm then extends these
rectangles maximally in both vertical directions and removes any rectangle
which are made redundant i.e. are completely covered by other rectangles in
the set.

For simple orthogonal polygons, we can find a hidden set of size at worst 1/2
the size of this. We simply place two sets of hidden points on all non-
collinear horizontal edges. In the case of collinearities within a set, just
choose 1 from each group of pairwise collinear edges. Ignore collinear edges
that do not see each other. The two sets comprise of one for the “top edges”
i.e. those which bound $P$ from above and “bottom edge” that bound from below.
If we place the hidden points at the midpoints of each edge, we know that no
two points on top edges will see each other because the line segment between
them must pass through the outside of $P$ near whichever of the two has a
lower $y$-coordinate. By symmetry, the same applies to the bottom edges. We
choose whichever of the two hidden sets is larger.

We show that there is at most $2hs(P)-1$ pieces in the convex partition of
size $p$, specifically one less than the total number of (noncollinear) top
edges and bottom edges. Let us say that the total number of these horizontal
edges is $e$, so $p\leq e-1$. We can show this by induction on $p$. This is
clearly holds for when $p=1$, as a rectangle with two edges and one piece,
$1\leq 2-1=1$. For the inductive step, consider the lowest rectangle in a
polygon $P$ with $k+1$ rectangles in its partition. Consider the polygon(s)
left when the lowest rectangle is removed. We will call this $P^{\prime}$ if
it is a single polygon, or $P_{1}^{\prime},P_{2}^{\prime},...,P_{m}^{\prime}$
if there are $m$ polygons left. There is two cases for this. In the first
case, the top edge of the removed rectangle is a proper subset of a lowest
bottom edge of $P^{\prime}$. See the left subfigure of Figure 13. We know that
for $P^{\prime}$, $p^{\prime}\leq e^{\prime}-1$. We know that $P$ has an
additional piece and an additional bottom edge, which means that $p-1\leq
e-1-1$ which in turn means $p\leq e-1$.

Figure 13: Showing the two cases for the induction. Left: Case 1, the top of
the lowest rectangle is a subset of a lowest edge of $P^{\prime}$. Right: Case
2, the top of the lowest rectangle is a superset of some lowest edges of
$P_{1}^{\prime},P_{2}^{\prime},...,P_{m}^{\prime}$

In the second case (see the right subfigure in Figure 13), the top edge of the
removed rectangle is a proper superset of some nonempty set of the lowest
edges from $P_{1}^{\prime},P_{2}^{\prime},...,P_{m}^{\prime}$. We know that
each of $P_{i}^{\prime}$ only shares 1 contiguous interval with the top of the
removed rectangle, since otherwise $P$ would have a hole. We know that for
each $P_{i}^{\prime}$, $p_{i}^{\prime}\leq e_{i}^{\prime}-1$. We know that $P$
contains 2 (noncollinear) edges not in any $P_{i}^{\prime}$, a top edge and a
bottom edge. The top edge of the removed rectangle cannot be fully covered by
the $P_{i}^{\prime}$s, since then there would be no splitting of $P$ to create
the removed rectangle. Each $P_{i}$ contains one edge that is along the top
edge of the removed rectangle (thus is not a true edge of $P$), which means
that $e=2+\sum(e_{i}^{\prime}-1)$, and the partition includes all, so
$p=1+\sum p_{i}^{\prime}$. From the previous inequality, we have:

$1+\sum p_{i}^{\prime}\leq 1+\sum(e_{i}^{\prime}-1)$ $p\leq e-1$

Therefore, since this holds for both cases, the claim holds by induction.

Therefore, simply taking the larger of the two sets of hidden points yields a
1/2 approximate solution for maximum hidden set and the set of rectangles form
a 2-approximation for minimum convex cover. This takes a total of $O(n\log n)$
time for both, as the hidden set can simply be implemented by sorting the
horizontal edges by $y$-coordinate and placing candidate hidden points on each
edge that is not collinear with its predecessor.

∎

###  3.9 Funnel Polygons

These results and those provided in Section 3.10 were originally presented in
an Arxiv submission by Browne [6]. We omit the pseudocode given there, as well
as the results on the restricted variants.

Funnel polygons are defined as simple polygons composed of a convex edge
$e_{n}=v_{n}v_{1}$ with two reflex chains $R_{1}=v_{1},v_{2},...,v_{t}$ and
$R_{2}=v_{t},...,v_{n-1},v_{n}$. Assume without loss of generality that $t\geq
n-t$, i.e. $|R_{1}|\geq|R_{2}|$. We will also assume that each reflex vertex
is strictly reflex, i.e. no three vertices within a chain are collinear and
there is a turn at every vertex. If this is not the case, we can simply remove
the vertices that are not strictly reflex. Funnel polygons are also sometimes
referred to as tower polygons.

We will use a recursive procedure to compute the hidden set and convex cover,
and thus will be able to prove the correctness of the algorithm using
induction. Our algorithm gives both a hidden set $H$ and a convex cover $C$,
but can be implemented to only find one. The algorithm finds both of these in
$O(n)$ time.

######  Theorem 3.9.

For any funnel polygon $P$, a hidden set $H$ in $P$ and a convex cover $C$ of
$P$ such that $|H|=|C|$ can be found in linear-time.

###### Proof.

The algorithm essentially determines a convex decomposition (with Steiner
points) such that for each piece in the decomposition, a hidden point can be
placed along either $R_{1}$ or $R_{2}$ corresponding to it.

The algorithm considers two cases. The first, easier case, is where all of the
edges $e_{i},e_{n-i}$ for $i\in[0,n-t]$ strongly see each other, i.e. they
form a convex quadrilateral $v_{i},v_{i+1},v_{n-i},v_{n-i+1}$ that is within
the polygon $P$. We will refer to this as the Case 1 and the case in which
this is not true as Case 2. We give two examples of Case 1 in Figure 14. If
this is the case, then we can simply place a hidden point on each midpoint of
$R_{1}$ (the longer chain) and connect the corresponding edges $e_{i},e_{n-i}$
until there are no more edges to connect across with from $R_{2}$. At this
point, we can simply partition the remaining region into triangles between the
remaining edges of $R_{1}$ and the vertex $v_{t+1}$.

Figure 14: Case 1 for the funnel polygons.

From here, we can use an induction on $n$, the number of vertices, to cover
Case 2 where not all edge pairs satisfy the strong visibility requirement of
Case 1. Clearly, when $n=3$, we have an instance of Case 1 and thus already
have a solution. From here we just need to show that if it holds for
$n\in[3,k]$, then it also holds for $n=k+1$. We can assume that for when
$n=k+1$, we do not have an instance of Case 1 since we have already shown
that. Let $e_{i},e_{n-i}$ be the lowest $i$ pair for which
$v_{i},v_{i+1},v_{n-i},v_{n-i+1}$ is not within $P$.

If $v_{i}$ does not see $v_{n-i+1}$, then the pair $e_{i-1}e_{n-i+1}$ would
also not have their quadrilateral within $P$ and $i-1<i$, so $v_{i}$ sees
$v_{n-i+1}$. If $v_{i+1}$ does not see $v_{n-i}$, then either $v_{i}$ does not
see $v_{n-i}$ or $v_{n-i+1}$ does not see $v_{i+1}$ because if there is an
internal vertex $u$ in the shortest path from $v_{i+1}$ to $v_{n-i}$, it must
be from either the chain of $R_{1}$ after $v_{i+1}$ or the chain of $R_{2}$
before $v_{n-i}$. This follows from [14, Lemma 1], since funnel polygons are a
subclass of polygons weakly visible from a convex edge. Because $R_{1}$ is a
reflex chain, if $u\in R_{1}$ then $u$ must also be in the shortest path from
$v_{i}$ to $v_{n-i}$. If $u\in R_{2}$, then $u$ must be in the shortest path
from $v_{n-i+1}$ to $v_{i+1}$. See Figure 15 for an example. Since these
shortest paths have internal vertices, the endpoints cannot see each other.

Figure 15: Lemma 1 of [14] implies that if $v_{i+1}$ does not see $v_{n-i}$
then either $v_{i}$ does not see $v_{n-i}$ or $v_{n-i+1}$ does not see
$v_{i+1}$. Figure 16: Case 2 for funnel polygons.

Therefore, since in all cases we find a convex cover and hidden set of the
same size, Theorem 3.9 holds. The algorithm runs in $O(n)$ time. First, note
that determining whether we are in Case 1 or Case 2 only takes $O(1)$ time per
edge in $P$. This is because the only way to be in Case 2 is if the edge
extension of one edge intersects with another edge, which takes $O(1)$ to
determine. We do not need to compare with any other edges of the polygon.
$P^{\prime}$ has complexity at most 1 less than $P$, which is only the case if
the index $i$ at which we form $P^{\prime}$ is 1, giving us the following
recurrence:

$T(n)=T(n-1)+O(1)$

The base case is $T(1)=O(1)$, which solves to a total runtime of $O(n)$.

∎

###  3.10 Pseudotriangles

Pseudotriangles are defined as simple polygons containing exactly 3 convex
vertices, which means that it can be represented as three reflex chains
$R_{1}=v_{1},v_{2},...,v_{t}$, $R_{2}=v_{t},...v_{s-1},v_{s}$,
$R_{3}=v_{s},...v_{n-1},v_{n}$. The three convex vertices here are
$v_{1},v_{t},$ and $v_{s}$. Without loss of generality, we will consider the
cardinalities of the chains to be such that $R_{1}\geq R_{2}\geq R_{3}$.
Funnel polygons are a subclass of pseudotriangles, where $|R_{3}|=1$. We will
only consider pseudotriangles that are not funnel polygons, as Section 3.9
already gives a linear-time algorithm for funnel polygons.

######  Theorem 3.10.

For any pseudotriangle $P$, a hidden set $H$ in $P$ and a convex cover $C$ of
$P$ such that $|C|\leq 2|H|$, i.e. a 2-approximation, can be found in linear-
time .

###### Proof.

We show that by using the algorithm for funnel polygons in Section 3.9, we can
achieve a linear-time 2-approximation for pseudotriangles. The procedure is
simple: Consider the edge $e_{1}=v_{1}v_{2}$, and its extension. The extension
of $e_{1}$ will land at some point $p$ on $R_{2}$ called $p$. It cannot land
on either $R_{1}$ or $R_{3}$ otherwise the landed on chain would not be
reflex, and it must intersect some part of the boundary of $P$. Let $p$ rest
on edge $e_{i}=v_{i}v_{i+1}$. This partitions $P$ into two subpolygons
$P_{1}=v_{2},v_{3}...v_{i},p$ and $P_{2}=p,v_{j+1},...v_{1}$. Both $P_{1}$ and
$P_{2}$ are composed of two reflex chains and a convex edge, making them both
funnel polygons. This is depicted in Figure 17.

Figure 17: Pseudotriangle partition into funnel polygons that allow for a
2-approximation.

From Theorem 3.9, we know that we can obtain from $P_{1}$ a hidden set $H_{1}$
and a convex cover $C_{1}$. By symmetry, $P_{2}$ we get $H_{2}$ and $C_{2}$.
As a hidden set, we take the larger, $H=\text{max}(H_{1},H_{2})$. As a convex
cover, we take the union, $H=C_{1}\cup C_{2}$. Because $|H_{1}|=|C_{1}|$ and
$|H_{2}|=|C_{2}|$, we know that $|C|\leq 2|H|$. This proves our claim, and
since finding $p$ takes at most $O(n)$ time, as does each funnel, the total
runtime is $O(n)$. ∎

Note, that while this algorithm does not achieve an exact answer, it is
impossible to have an algorithm that only places hidden points on the edges of
a pseudotriangle and that finds the exact maximum hidden set. The famous GFP
(Godfried’s Favorite Polygon) counterexample suffices here, and we depict it
in Figure 18. We give a convex cover of the boundary of size 3, which means
that any hidden set constrained to the boundary must have size at most 3. We
also give a hidden set of size 4, which means that 3 pieces cannot suffice for
a convex cover.

Figure 18: Godfried’s favorite polygon, with a convex cover of the boundary of
size 3 and a hidden set of size 4.

Therefore, any algorithm that places hidden points only on the boundary of a
pseudotriangle cannot achieve an approximation factor better than $4/3$.

##  4 Conclusion

Polygon class | Inequality | Worst known ratio $(cc(P)/hs(P))$
---|---|---
Histogram polygons [7] | $hs(P)\leq cc(P)\leq hs(P)$ | 1
Spiral polygons[7] | $hs(P)\leq cc(P)\leq hs(P)$ | 1
Funnel[6] | $hs(P)\leq cc(P)\leq hs(P)$ | 1
Monotone Mountains (or Rocking Chairs) | $hs(P)\leq cc(P)\leq hs(P)$ | 1
Convex Fans | $hs(P)\leq cc(P)\leq hs(P)$ | 1
Star-shaped polygons | $hs(P)\leq cc(P)\leq 2\cdot hs(P)$ | 3/2
Simple orthogonal polygons | $hs(P)\leq cc(P)\leq 2\cdot hs(P)$ | 4/3
Pseudotriangles[6] | $hs(P)\leq cc(P)\leq 2\cdot hs(P)$ | 1
Polygons weakly visible from a convex edge | $hs(P)\leq cc(P)\leq 2\cdot hs(P)$ | 1
Weak visibility polygons | $hs(P)\leq cc(P)\leq 4\cdot hs(P)$ | 3/2
Simple polygons | $hs(P)\leq cc(P)\leq 8\cdot hs(P)$ | 3/2
Polygons with holes | $hs(P)\leq cc(P)\leq h\cdot hs(P)$ | 3/2
Table 1: The bounds between hidden set and convex cover for various polygon
types ($h$ is the number of holes)

We showed several extensions of previous positive and negative results for the
minimum convex cover problem and the maximum hidden set problem. In addition
to the algorithmic results, we give their implied combinatorial results in
Table 1. The most pressing open problem with respect to both problems is
whether or not there exists a constant factor approximation for convex cover
in polygons with holes or there is additional hardness of approximation. It is
clear from the $n^{epsilon}$ hardness for maximum hidden set that any attempt
to use maximum hidden set as a bound as is done for the simple polygon case is
doomed to fail unless $P=NP$. Additionally, due to the runtime for the $O(\log
n)$ approximation being prohibitively large for implementation, it would also
be interesting to see if there can be an improvement of the runtime for that.

With respect to hidden set, the most interesting problem is whether the
problem is in fact in NP. Currently, it is not known whether the problem is in
NP or if it is $\exists\mathbb{R}$-hard. Most proofs of
$\exists\mathbb{R}$-hardness for geometric problems show as a byproduct that
even polygons with rational coordinates can sometimes admit solutions which
involve irrational points. However, there always exists solutions to the
maximum hidden set problem in which all of the points have rational
coordinates. This is because in order to be hidden, each point must have a
corresponding neighborhood around it of nonzero radius for which none of the
other hidden points can see any part of. This allows for the iterative
transformation of any set of hidden points into one which has entirely
rational coordinates. This discourages the chances that solutions to all
$\exists\mathbb{R}$ formulas can be expressed as maximum hidden sets. However,
there is no guarantee that these rational coordinates have fixed complexity
with respect to the input coordinates, so it is not entirely clear how to
prove NP-membership.

## References

  * [1] Mikkel Abrahamsen.  Covering polygons is even harder.  2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 375–386, 2022.
  * [2] Mikkel Abrahamsen, William Bille Meyling, and André Nusser.  Constructing Concise Convex Covers via Clique Covers.  In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry (SoCG 2023), volume 258 of Leibniz International Proceedings in Informatics (LIPIcs), pages 66:1–66:9, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [3] Carlos Alegría, Pritam Bhattacharya, and Subir Kumar Ghosh.  A 1/4-approximation algorithm for the maximum hidden vertex set problem in simple polygons.  In European Workshop on Computational Geometry, 2019.
  * [4] Jan Van Den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford.  A deterministic almost-linear time algorithm for minimum-cost flow.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 503–514, 2023.
  * [5] R. Browne, P. Kasthurirangan, J. B. Mitchell, and V. Polishchuk.  Constant-factor approximation algorithms for convex cover and hidden set in a simple polygon.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1357–1365, Los Alamitos, CA, USA, nov 2023. IEEE Computer Society.
  * [6] Reilly Browne.  Convex cover and hidden set in funnel polygons, 2023.
  * [7] Reilly Browne and Eric Chiu.  Collapsing the hidden-set convex-cover inequality.  In Proceedings of the 38th Computational Geometry Young Researchers Forum (CG:YRF 2022), pages 27–32. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2022.
  * [8] J.C. Culberson and R.A. Reckhow.  Covering polygons is hard.  In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pages 601–611, 1988.
  * [9] R. P. Dilworth.  A decomposition theorem for partially ordered sets.  Ann. of Math., 51(1):161–166, 1950.
  * [10] Stephan Eidenbenz.  Inapproximability of finding maximum hidden sets on polygons and terrains.  Computational Geometry, 21(3):139–153, 2002.
  * [11] Stephan J. Eidenbenz and Peter Widmayer.  An approximation algorithm for minimum convex cover with logarithmic performance guarantee.  SIAM Journal on Computing, 32(3):654–670, 2003.
  * [12] D. S. Franzblau.  Performance guarantees on a sweep-line heuristic for covering rectilinear polygons with rectangles.  SIAM Journal on Discrete Mathematics, 2(3):307–321, 1989.
  * [13] Frederick S. Gella and Rosalio G. Artes.  Clique cover of graphs.  Applied mathematical sciences, 8:4301–4307, 2014.
  * [14] Subir Kumar Ghosh, Anil Maheshwari, Sudebkumar Prasant Pal, Sanjeev Saluja, and C.E. Veni Madhavan.  Characterizing and recognizing weak visibility polygons.  Computational Geometry, 3(4):213–233, 1993.
  * [15] Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert Endre Tarjan.  Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons.  Algorithmica, 2:209–233, 1987.
  * [16] D. Lee and F. Preparata.  An optimal algorithm for finding the kernel of a polygon.  Journal of the ACM (JACM), 26:415–421, 07 1979.
  * [17] Joseph S. B. Mitchell, Valentin Polishchuk, and Mikko Sysikaski.  Minimum-link paths revisited.  Computational Geometry, 47(6):651–667, 2014.  Special issue on EuroCG’11.
  * [18] T. Shermer.  Hiding people in polygons.  Computing, 42(2-3):109–131, 1989.
  * [19] Subhash Suri.  A linear time algorithm for minimum link paths inside a simple polygon.  Computer Vision, Graphics, and Image Processing, 35(1):99–110, 1986.