2021

[1]Chinmoy Deka

[1]Abhishek Shrivastava

[1]Department of Design, Indian Institute of Technology Guwahati, 781039,
Assam, India

2]Center for Intelligent Cyber Physical Systems, Indian Institute of
Technology Guwahati, 781039, Assam, India

# AI-Based Automated Speech Therapy Tools for persons with Speech Sound
Disorders: A Systematic Literature Review

<EMAIL_ADDRESS><EMAIL_ADDRESS>Saurabh Nautiyal
<EMAIL_ADDRESS>Praveen Chauhan<EMAIL_ADDRESS>*  [

###### Abstract

This paper presents a systematic literature review of published studies on AI-
based automated speech therapy tools for persons with speech sound disorders
(SSD). The COVID-19 pandemic has initiated the requirement for automated
speech therapy tools for persons with SSD making speech therapy accessible and
affordable. However, there are no guidelines for designing such automated
tools and their required degree of automation compared to human experts. In
this systematic review, we followed the PRISMA framework to address four
research questions: 1) what types of SSD do AI-based automated speech therapy
tools address, 2) what is the level of autonomy achieved by such tools, 3)
what are the different modes of intervention, and 4) how effective are such
tools in comparison with human experts. An extensive search was conducted on
digital libraries to find research papers relevant to our study from 2007 to
2022. The results show that AI-based automated speech therapy tools for
persons with SSD are increasingly gaining attention among researchers.
Articulation disorders were the most frequently addressed SSD based on the
reviewed papers. Further, our analysis shows that most researchers proposed
fully automated tools without considering the role of other stakeholders. Our
review indicates that mobile-based and gamified applications were the most
frequent mode of intervention. The results further show that only a few
studies compared the effectiveness of such tools compared to expert Speech-
Language Pathologists (SLP). Our paper presents the state-of-the-art in the
field, contributes significant insights based on the research questions, and
provides suggestions for future research directions.

###### keywords:

AI-based Speech Therapy, Speech Sound Disorders, Automatic Speech Therapy

##  1 Introduction

Speech Sound Disorder (SSD) refers to difficulties with perception, motor
production, phonological representation of speech sounds, and speech segments.
In short, a person with SSD finds it difficult to produce or use some sounds
correctly. According to the American Speech-Language-Hearing Association
(ASHA), SSD can be organic and functional on1 . While organic SSD result from
an underlying motor/neurological, structural, or sensory/perceptual cause,
there is no known cause for functional SSD on1 (see Figure 1). The prevalence
of SSD varies significantly according to different studies; however, these
studies reflect the magnitude of the problem. Multiple studies have estimated
that residual or persistent speech errors occur in 1% to 2% of older children
and adults flipsen2015emergence . In various studies overall, 2.3% to 24.6% of
school-aged children were estimated to have speech delay or speech sound
disorders ref_2 ; ref_3 . In a 2012 survey, National Center for Health
Statistics found that 48.1% of 3 to 10-year-old children and 24.44% of 11 to
17-year-old children had speech sound problems ref_2 . According to the 2011
census, in India, hearing impairment (18.9 %) was the second leading
disability, and speech impairment (7.5 %) was the fifth-highest disability
ref_4 . In another survey conducted in India’s rural population, the
researchers of All India Institute of Speech and Hearing (AIISH), Mysore,
found that around 6.07 % were at risk of communication disorders, including
speech sound disorder ref_5 .

Figure 1: Classification of Speech Sound Disorders

In addressing such speech impairments, Speech-Language Pathologists (SLPs)
play a significant role in the screening, assessment, diagnosis, and treatment
of persons with SSD. Personalized speech therapy and practice monitored by
SLPs can improve the acquisition of speech skills ref_6 . However, the
accessibility of SLPs is crucial for such intervention. A report suggests that
up to 70 % of SLPs have waiting lists, which indicates a shortage in the
workforce ref_6 ; ref_7 . Furthermore, according to United Nations Children’s
Fund (UNICEF), there are not adequate speech-language therapy services for
children with communication disorders and disabilities unicef . Moreover,
speech therapy involves extended interactions and multiple sessions with SLPs.
Such therapy requires extensive time, making it expensive and inaccessible for
persons living in impoverished and rural areas. Addressing these issues of
accessibility and expensiveness, many researchers have proposed AI-based
automated tools for providing speech therapy autonomously to persons with SSD.
With the advent of improved ASR tools, impaired speech datasets, and AI-based
techniques, it is now possible to build such autonomous tools for speech
therapy. These autonomous tools embedded in mobile devices or provided as
cloud services can be revolutionary in making speech therapy accessible and
affordable.

This paper reviews the research involving AI-based automated speech therapy
tools for persons with SSD during the last 15 years. In the next section 2, we
present the methodology adopted in this study. Section 3 reports the results
and Section 4 presents the discussion. Finally, we conclude the study in
Section 5.

##  2 Methodology

We followed the PRISMA protocol to perform the systematic literature review to
achieve higher transparency and reliability prisma . We included studies that
can cover one of the following questions we framed for this systematic
literature review.

  * •

RQ1: What types of SSD do AI-based automated speech therapy tools address?

  * •

RQ2: What is the level of autonomy achieved by such tools?

  * •

RQ3: What are the different modes of intervention (delivery modes: mobile,
computer, robots, etc., and presentation modes: games, storytelling, etc.)?

  * •

RQ4: How effective are such tools with respect to human experts (SLPs)?

###  2.1 Eligibility Criteria

####  2.1.1 Types of Studies

We considered full articles, review papers, and short papers which proposed
automated speech therapy tools using AI techniques such as machine learning
and deep learning. The studies were restricted to articles written in English
and published from 2007 to 2022 (research carried out over the last 15 years).
The objective is to provide a snapshot of the research domain. We carried out
the final search on February 4th, 2022.

####  2.1.2 Types of Participants

We included participants of any age and gender with SSD, such as articulation
disorder, phonological disorder, apraxia, dysarthria, cleft palate, and
hearing impairment. However, we excluded studies specifically addressing
cognitive conditions such as Alzheimer’s disease, Down’s syndrome, Parkinson’s
disease, and Autism Spectrum Disorders.

####  2.1.3 Types of Intervention

We didn’t restrict on types of intervention and included all studies that
proposed automated speech therapy using different intervention methods.
Studies included robotics-based, mobile-based, computer-based interventions
along with gamified and story-based intervention methods.

###  2.2 Information Sources

The studies were identified by searching electronic databases using the search
term generated using keywords from the research questions. The search string
was applied to Scopus, IEEE Xplore, and ACM Digital Library electronic
databases. The results from the databases were extracted, and
inclusion/exclusion criteria were applied to find relevant studies.

###  2.3 Search Terms

The following keywords were used to search all the databases: speech,
language, disorder, impairment, assessment, therapy, rehabilitation,
treatment, AI, artificial intelligence, automated, automatic. Boolean
operators were used to combine the terms as: (”AI” OR ”Artificial
Intelligence” OR ”automa*”) AND (”speech” OR ”language”) AND (”disorder” OR
”impairment”) AND (”assessment” OR ”therapy” OR ”rehabilitation” OR
”treatment”).

###  2.4 Study Selection and Data Collection

We found a total of 763 research studies from individual databases, i.e., 635
from Scopus, 72 from IEEE Xplore, and 56 from the ACM Digital Library. Then we
removed duplicates and corrupt entries to find 678 papers for the screening
phase. We performed the screening of the studies in three stages. At first,
two authors screened the titles, which resulted in 238 research studies. Two
authors reviewed abstracts in the next screening stage, which resulted in 94
research studies. Finally, all four authors reviewed the full texts of the 94
articles. After applying the inclusion and exclusion criteria for this
systematic literature review, we selected 24 research studies. Disagreements
during the screening process were resolved by discussion and voting by all the
authors. Figure 2 shows all the phases: ”identification,” ”screening,” and
”included” according to the PRISMA protocol prisma .

Figure 2: Prisma Systematic Review Process applied to 763 papers

##  3 Results

We report our results in five different sections. In the first section 3.1, we
analyzed the included papers with respect to paper counts, authors, regions,
languages, and venues. In the following sections (see 3.2,3.3,3.4,3.5), we
present our findings based on the research questions addressed in this
systematic literature review.

###  3.1 Paper Counts, Authors, Regions, Languages, and Venues

The final papers selected after the full review were 24 papers from 23
different venues. The number of studies on AI-Based automated speech therapy
tools for persons with SSD published shows an upward trend over the years (see
Figure 3). Out of 24 papers, we can observe that 20 articles were published
during the last 6-7 years.

Figure 3: Number of papers according to the year of publication

The majority of the paper included in this study were published in journals
(see figure 4). Additionally, there were ten papers published in conference
proceedings and two book chapters among the 24 included studies. However, we
could not find any eligible studies published in a magazine.

Figure 4: Number of papers by publication type

There were 91 unique authors identified from the included studies. The
VOSviewer software was used to calculate the most impactful authors, generate
co-authorship clusters, and perform co-occurrences of keyword analysis vos .
All the authors were counted irrespective of the authorship order with the
same weightage applied to all the authors. However, high weightage was
attributed to authors publishing more articles. In addition, to find the list
of most impactful authors, their collaborating links were also considered,
along with the number of published documents. The top ten most impactful
authors are listed in the table 1. The most significant cluster of authors
based on the number of articles and collaborative link strength was found, as
shown in the figure 5. It is worth noting that 79 authors (86.81 %)
contributed to only one paper in the included studies, i.e., have only one
work relating to AI-based automated speech therapy in the last 15 years.
Moreover, after analyzing the author’s keywords of the included studies, the
most significant cluster of linked and co-occurred keywords was found as shown
in the figure 6. The most significant keyword was ASR(Automatic Speech
Recognition).

Table 1: Top ten most impactful authors Author | Documents | Total Link Strength
---|---|---
Lopez-Nores, M. | 4 | 18
Pazos-arias, J. | 4 | 18
Robles-Bykbaev, V. | 4 | 18
Guaman-Heredia, M | 2 | 11
Quasi-peralta, D. | 2 | 11
Lee, T. | 2 | 10
Ng, C.W.Y. | 2 | 10
Ng, S.I. | 2 | 10
Wang, J. | 2 | 10
Garcia-duque, Jorge | 2 | 9
Figure 5: Main cluster of co-authorship analysis Figure 6: Main cluster of co-
occurrences of keyword analysis

We further report the geographical distribution of the included studies based
on the location of the study indicated in the paper (see figure 7). We looked
at the author’s affiliation and funding agency when required. Most papers
reported on studies which were conducted in Europe (11 papers) and North
America (6 papers). Studies conducted in Europe include four studies from
Spain and one study each from Germany, Hungary, Romania, Portugal, the Czech
Republic, and Italy. On the other hand, studies from North America include
four studies from the USA, one collaborative study between Panama and
Nicaragua, and another study from Mexico. Moreover, five papers reported
studies in Asia, which includes China (2 studies), India (1 study), Taiwan (1
study), and the Philippines (1 study). However, other continents are heavily
underrepresented; Africa and Oceanic each have one study conducted. Finally,
we could not find any eligible studies meeting our selection criteria which
were conducted in South America.

Figure 7: Geographical distribution of the papers Figure 8: Language
distribution of the papers

We presented the language distribution of the papers based on the language
addressed by the AI-based automated speech therapy tools as reported in the
studies (see figure 8). The most addressed languages were English (10 studies)
and Spanish (4 studies). Furthermore, two studies addressed the Cantonese
language, and there was only one study each for Punjabi, German, Hungarian,
Romanian, Portuguese, Italian, Arabic, and Mandarin. The studies were drawn
from 23 unique venues. We could observe that the vast majority of venues from
which papers were chosen (95.65%) were represented by only one article. Only
one venue, i.e., ”Studies in Health Technology and Informatics,” had published
two papers included in this review.

###  3.2 Speech Sound Disorders (RQ1)

We found that researchers have addressed multiple types of SSD in the
literature. However, 12 studies out of 24 studies did not address any specific
SSD (see figure 9). These studies proposed automated tools for a generalized
SSD population and experimented without specifying any particular SSD ref_7 ;
ref_8 ; ref_9 ; ref_10 ; ref_11 ; ref_12 ; ref_13 ; ref_14 ; ref_15 ; ref_16 ;
ref_17 ; ref_18 . Researchers have also specifically worked and devised AI-
based tools for persons with hearing impairment ref_19 ; ref_20 . A novel
tongue-based Human-Computer interaction tool ref_21  and gamified AI-based
tool ref_6  for persons with motor speech disorder have been proposed.

Figure 9: Distribution of papers addressing generalized and specific SSD

Moreover, Frieg et al. proposed a digital training system for dysarthric
patients ref_22 . In another similar study, Saz et al. devised ASR-based tools
and technologies and conducted user studies specifically for dysarthric
patients ref_23 . Singh et al. and Chen et al. developed and assessed
automatic AI-based speech therapy tools for articulation disorder in Punjabi
and Mandarin, respectively ref_24 ; ref_25 . Ballard et al. conducted a
feasibility study of a tablet-based automated feedback tool for apraxia
patients ref_26 . On the other hand, Ramamurthy et al. developed a novel
companion robot, ”Buddy,” for cleft lip and palate disorder children ref_27 .
In another study, Rivas et al. proposed using a virtual world to provide
speech therapy for children with dyslalia rivas2012proposal . It is worth
noting that only one study was related to speech data collection for Cantonese
to perform phonology and articulation assessment ref_9 . The figure 10 shows
the distribution of papers addressing specific SSD.

Figure 10: Distribution of papers addressing specific SSD

###  3.3 Level of Autonomy (RQ2)

Researchers worldwide have amplified the debate between autonomy vs. human
control due to the risks and concerns associated with AI and large-scale
automation ref_28 . In this area concerning automation and AI in speech
therapy, we studied the level of autonomy achieved by AI-based automated
speech therapy tools. In many studies, researchers build fully automated AI-
based speech therapy tools without considering the role of parents, SLPs, and
other stakeholders. While Desolda et al. emphasized the role of caregivers and
SLP in the design of a remote therapy tool, ”Pronuntia” ref_8 , Ng et al.
proposed a fully automated assessment tool using the CUChild 127 speech corpus
in Cantonese ref_10 . In another study, Bilkova et al. developed a novel lip,
tongue, and teeth detection system using Convolutional Neural Network (CNN)
and Augmented Reality (AR) for supporting the automatic evaluation of speech
therapy exercises ref_21 .

Furthermore, Sztaho et al. proposed a fully automated speech therapy tool by
displaying visual feedback on intensity(accent), intonation, and rhythm to
children with hearing impairments ref_19 . In another similar study, Hernández
et al. developed a serious game with an automatic feedback feature for
hearing-impaired children ref_20 . Ballard et al. performed a feasibility
study of their tablet-based, fully automated therapy tool for children with
apraxia without any role of SLP and other stakeholders ref_26 . Moreover, V.
Robles-Bykbaev et al. proposed a framework imitating the main functionality of
SLP along with a robotic assistant motivating children in therapy activity and
automatically giving real-time feedback ref_7 ; ref_14 ; ref_13 ; ref_15 . In
another similar study, Ramamurthy et al. proposed a companion robot, ”Buddy,”
which automatically evaluates speech exercises of children with CL/P disorders
with the feature of monitoring by SLPs ref_27 .

###  3.4 Modes of Intervention (RQ3)

Researchers have adopted different modes of intervention while implementing
AI-based automated speech therapy tools for persons with SSD. As these
therapies are often targeted at children, researchers emphasize developing
tools that trigger excitement and build companionship. Desolda et al. proposed
a web application for children, SLPs, and caregivers, allowing SLP to assign
therapy exercises to children with SSD ref_8 . The system automatically
evaluates the correctness of the exercises and gives real-time feedback. On
the other hand, Ballard et al. proposed a tablet-based therapy tool for
children with apraxia ref_26 . Furthermore, Ng et al. and Sztaho et al.
proposed a computer-based prosody teaching system for children with hearing
impairment and a computer-based visual feedback system for the hearing
impaired, respectively ref_10 ; ref_19 . Bykbaev et al. proposed a novel
robotic assistant along with a fully automatic framework imitating the work of
SLP ref_7 . In another similar study, Ramamurthy et al. proposed a therapy
robot, ”Buddy,” allowing children to practice assigned exercises at home
ref_27 . Many studies have incorporated serious games as an intervention tool
for automatic speech therapy ref_29 ; ref_21 ; ref_27 ; ref_6 ; ref_17 . One
of the studies incorporated augmented reality to build a serious game using
tongue detection ref_21 .

Figure 11: Distribution of papers based on modes of intervention

###  3.5 Effectiveness (RQ4)

The effectiveness of AI-based automated speech therapy tools depends on their
performance compared to SLPs. Moreover, automated speech therapy tools
providing wrong feedback can be disastrous to children’s speech improvement.
Few studies (4 out of 24) compared the results of their automated tool with
human experts (SLPs) (see figure 12). Ballard et al. conducted an interrater
agreement test between their ASR tool and SLPs and found ASR-human agreement
averaged 80% ref_26 . In another study, Sztaho et al. found that their
automated tool scores correspond to the subjective evaluation by SLPs ref_19 .
Bykbaev et al. found that over 90% of the therapy plans generated
automatically by their expert ”Spelta” were ”better than” or ”as good as ”
what the SLPs would have created manually ref_14 . Moreover, in the study by
Saz et al., their Automatic Speech Recognition (ASR) and Pronunciation
Verification (PV) modules based on impaired speech utterances provided
performance similar to SLPs ref_23 .

Figure 12: Distribution of papers comparing AI results with human experts

##  4 Discussion

We conducted this systematic literature review based on a sample of 24 out of
678 research papers deriving from Scopus, IEEEXplore, and ACM DL databases.
Exciting insights and trends emerged from our analysis of these papers. In
recent years, we observed an increasing interest in AI-based automated speech
therapy tools. This growing interest can be due to the recent advancement in
ASR technology and its improved accuracy. Surprisingly, 79 authors (86.81%)
out of 91 unique authors have only one work on AI-based automated speech
therapy in the last 15 years. This data suggests that a significant amount of
research in this field is ”one-off” by authors. Most authors explored the
research area with one idea and did not develop or evaluate it further. We
found that ”automatic speech recognition” is the most emphasized keyword by
the authors. This finding is consistent with the notion that ASR is the core
of AI-based automated speech therapy tools. The majority of studies were from
European, North American, and Asian countries, and the most prevalent language
targeted by the included studies was English. This finding is in line with the
fact that English is the most widely adopted language for ASR technologies
benzeghiba2007automatic . However, we can also observe that researchers have
attempted to build AI-based automated speech therapy tools in other languages.

Furthermore, we found that articulation disorder was the most frequent
disorder addressed by the included studies, with three studies dedicated to
them. This may be due to the fact that articulation disorder are commonly
found in persons with other SSD flipsen2015emergence . The results show that
most studies aimed at developing fully automated speech therapy tools without
considering the role of other stakeholders such as speech-language
pathologists, caretakers, parents, and family members. This finding is in line
with the widespread belief that researchers traditionally follow the one-
dimensional framework of levels of automation by Sheridon and Verplank, which
suggests that more automation leads to less human control and vice versa
sheridan1978human . Moreover, a fully automated system may bring multiple
concerns, such as biased data, privacy, replacement of jobs, and extreme
automation may lead to disastrous consequences ref_28 . In the case of AI-
based automated speech therapy, many concerns arise, including biased speech
data, replacement of SLPs, and privacy of children’s speech data. We further
found that mobile-based deployment of AI-based automated speech therapy was
more common among the included studies. A possible explanation is that
researchers are more interested in building affordable and accessible
automated speech therapy tools. Another significant issue we observed is that
few studies compared their automated tools’ results with human experts such as
SLPs. This considerable insight questions the effectiveness of automated AI-
based speech therapy tools compared to expert SLPs.

There are some limitations in our study which is worth mentioning. We relied
on three databases: ACM DL, IEEE Xplore, and Scopus; therefore, we may have
missed relevant papers published in other databases. Another limitation is the
in-applicability of quality appraisal methods such as the ”Risk of Bias
Assessment” in our study, as in the case of health sciences. Furthermore, our
study restricts papers addressing SSD defined by ASHA and excluded studies
addressing other related disorders.

##  5 Conclusion

This systematic literature review was based on the PRISMA Statement to analyze
papers on AI-based automated speech therapy tools for persons with SSD. We
extracted relevant data from the included articles based on four predefined
research questions: Types of SSD addressed; Level of autonomy achieved by such
tools; Modes of interventions and Effectiveness of such tools. Our study
answers all the predefined research questions providing a snapshot of the
research carried out in the domain. We found that articulation disorder,
hearing impairment, dysarthria, and motor speech were the most frequently
studied disorders, addressed in three, two, two, and two studies (research
question 1). However, 50% of the studies did not address any specific SSD.
Concerning the level of autonomy (research question 2), almost all studies
proposed fully-automated AI-based speech therapy tools suggesting that
researchers did not emphasize the role of caretaker, parents, family members,
and SLPs. Addressing the modes of intervention (research question 3), most
researchers proposed mobile-based and computer-based applications. Finally,
the analysis of the effectiveness (research question 4) of such AI-based
speech therapy tools provides us the insights that very few studies have
compared their proposed system’s effectiveness with expert SLPs.

Based on the findings and insights from our research questions, we propose the
following directions for future research on AI-based automated speech therapy
tools.

  * •

Development of speech corpora and AI-based automated speech therapy tools for
under-represented languages and its deployment in under-developed regions
where the shortage of SLPs prevails.

  * •

Development of such tools for specific SSD instead of generalized SSD.

  * •

Implementation of a Human-Centered AI approach in developing such tools, i.e.,
involving all stakeholders in the design process instead of focussing on
developing fully automated tools.

  * •

Conducting usability studies for understanding the effectiveness of different
modes of delivery (mobile device, computer, companion robots) and different
modes of presentation (gamified content, storytelling).

  * •

Development of a robust framework for measuring the effectiveness of such
tools with respect to SLPs.

##  6 Conflict of interest

On behalf of all authors, the corresponding author states that there is no
conflict of interest

## References

  *   * (1) Speech Sound Disorder. https://www.asha.org/public/speech/disorders/speech-sound-disorders/. Accessed: 2022-02-28
  * (2) Flipsen Jr, P.: Emergence and prevalence of persistent and residual speech errors. In: Seminars in Speech and Language, vol. 36, pp. 217–223 (2015). Thieme Medical Publishers
  * (3) Black, L.I., Vahratian, A., Hoffman, H.J.: Communication disorders and use of intervention services among children aged 3-17 years: United states, 2012. nchs data brief. number 205. Centers for Disease Control and Prevention (2015)
  * (4) Wren, Y., Miller, L.L., Peters, T.J., Emond, A., Roulstone, S.: Prevalence and predictors of persistent speech sound disorder at eight years old: Findings from a population cohort study. Journal of Speech, Language, and Hearing Research 59(4), 647–673 (2016)
  * (5) Velayutham, B., Kangusamy, B., Joshua, V., Mehendale, S.: The prevalence of disability in elderly in india–analysis of 2011 census data. Disability and health journal 9(4), 584–592 (2016)
  * (6) Sreeraj Konadath, S.C., Jayaram, G., Sandeep, M., Mahima, G., Shreyank, P.: Prevalence of communication disorders in a rural population of india. Journal of Hearing Science 3(2) (2013)
  * (7) Duval, J., Rubin, Z., Segura, E.M., Friedman, N., Zlatanov, M., Yang, L., Kurniawan, S.: Spokeit: building a mobile speech therapy experience. In: Proceedings of the 20th International Conference on Human-Computer Interaction with Mobile Devices and Services, pp. 1–12 (2018)
  * (8) Robles-Bykbaev, V., Guamán-Heredia, M., Robles-Bykbaev, Y., Lojano-Redrován, J., Pesántez-Avilés, F., Quisi-Peralta, D., López-Nores, M., Pazos-Arias, J.: Onto-speltra: A robotic assistant based on ontologies and agglomerative clustering to support speech-language therapy for children with disabilities. In: Colombian Conference on Computing, pp. 343–357 (2017). Springer
  * (9) Groce, N., Deluca, M., Colde, E., Berman-Bieler, R., Mitra, G., Farkas, A., Sabbe, L., Burlyaeva-Norman, A., Lansdown, G.: Children and young people with disabilities: Fact sheet (UNICEF). https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.799.7313&rep=rep1&type=pdf. Accessed: 2022-02-28 (2013)
  * (10) Shamseer, L., Moher, D., Clarke, M., Ghersi, D., Liberati, A., Petticrew, M., Shekelle, P., Stewart, L.A.: Preferred reporting items for systematic review and meta-analysis protocols (prisma-p) 2015: elaboration and explanation. Bmj 349 (2015)
  * (11) Van Eck, N.J., Waltman, L.: VOSviewer Manual. https://www.vosviewer.com. Accessed: 2022-02-28
  * (12) Desolda, G., Lanzilotti, R., Piccinno, A., Rossano, V.: A system to support children in speech therapies at home. In: CHItaly 2021: 14th Biannual Conference of the Italian SIGCHI Chapter, pp. 1–5 (2021)
  * (13) Ng, S.-I., Ng, C.W.-Y., Wang, J., Lee, T., Lee, K.Y.-S., Tong, M.C.-F.: Cuchild: A large-scale cantonese corpus of child speech for phonology and articulation assessment. arXiv preprint arXiv:2008.03188 (2020)
  * (14) Ng, S.I., Tao, D., Wang, J., Jiang, Y., Ng, W.Y., Lee, T.: An automated assessment tool for child speech disorders. In: 2018 11th International Symposium on Chinese Spoken Language Processing (ISCSLP), pp. 493–494 (2018). IEEE
  * (15) Mahmut, E.E., Nicola, S., Stoicu-Tivadar, V.: A computer-based speech sound disorder screening system architecture. Data, Informatics and Technology: An Inspiration for Improved Healthcare, 39–42 (2018)
  * (16) Das, M., Saha, A.: An automated speech-language therapy tool with interactive virtual agent and peer-to-peer feedback. In: 2017 4th International Conference on Advances in Electrical Engineering (ICAEE), pp. 510–515 (2017). IEEE
  * (17) Robles-Bykbaev, V.E., Guamán-Murillo, W., Quisi-Peralta, D., López-Nores, M., Pazos-Arias, J.J., García-Duque, J.: An ontology-based expert system to generate therapy plans for children with disabilities and communication disorders. In: 2016 IEEE Ecuador Technical Chapters Meeting (ETCM), pp. 1–6 (2016). IEEE
  * (18) Robles-Bykbaev, V., López-Nores, M., García-Duque, J., Pazos-Arias, J.J., Arévalo-Lucero, D.: Evaluation of an expert system for the generation of speech and language therapy plans. JMIR medical informatics 4(3), 5660 (2016)
  * (19) Robles-Bykbaev, V.E., López-Nores, M., Pazos-Arias, J.J., Arévalo-Lucero, D.: Spelta: An expert system to generate therapy plans for speech and language disorders. Expert Systems with Applications 42(21), 7641–7651 (2015)
  * (20) Seddik, A.F., El Adawy, M., Shahin, A.I.: A computer-aided speech disorders correction system for arabic language. In: 2013 2nd International Conference on Advances in Biomedical Engineering, pp. 18–21 (2013). IEEE
  * (21) Duval, J.: Approaches for creating therapy games. ACM SIGACCESS Accessibility and Computing (126), 1–1 (2020)
  * (22) Samonte, M.J.C., Bahia, R.J.D., Forlaje, S.B.A., Del Monte, J.G.J., Gonzales, J.A.J., Sultan, M.V.: Assistive mobile app for children with hearing & speech impairment using character and speech recognition. In: Proceedings of the 4th International Conference on Industrial and Business Engineering, pp. 265–270 (2018)
  * (23) Sztahó, D., Kiss, G., Vicsi, K.: Computer based speech prosody teaching system. Computer Speech & Language 50, 126–140 (2018)
  * (24) Céspedes-Hernández, D., Pérez-Medina, J.L., González-Calleros, J.M., Rodríguez, F.J.Á., Muñoz-Arteaga, J.: Sega-arm: A metamodel for the design of serious games to support auditory rehabilitation. In: Proceedings of the XVI International Conference on Human Computer Interaction, pp. 1–8 (2015)
  * (25) Bílková, Z., Novozámskỳ, A., Bartoš, M., Domínec, A., Greško, Š., Zitová, B., Paroubková, M., Flusser, J.: Human computer interface based on tongue and lips movements and its application for speech therapy system. Electronic Imaging 2020(1), 389–1 (2020)
  * (26) Frieg, H., Muehlhaus, J., Ritterfeld, U., Bilda, K.: Isi-speech: A digital training system for acquired dysarthria. In: AAATE Conf., pp. 330–334 (2017)
  * (27) Saz, O., Yin, S.-C., Lleida, E., Rose, R., Vaquero, C., Rodríguez, W.R.: Tools and technologies for computer-aided speech and language therapy. Speech Communication 51(10), 948–967 (2009)
  * (28) Singh, S., Thakur, A., Vir, D.: Automatic articulation error detection tool for punjabi language with aid for hearing impaired people. International Journal of Speech Technology 18(2), 143–156 (2015)
  * (29) Chen, Y.-J., Huang, J.-W., Yang, H.-M., Lin, Y.-H., Wu, J.-L.: Development of articulation assessment and training system with speech recognition and articulation training strategies selection. In: 2007 IEEE International Conference on Acoustics, Speech and Signal Processing-ICASSP’07, vol. 4, p. 209 (2007). IEEE
  * (30) Ballard, K.J., Etter, N.M., Shen, S., Monroe, P., Tien Tan, C.: Feasibility of automatic speech recognition for providing feedback during tablet-based treatment for apraxia of speech plus aphasia. American journal of speech-language pathology 28(2S), 818–834 (2019)
  * (31) Ramamurthy, P., Li, T.: Buddy: a speech therapy robot companion for children with cleft lip and palate (cl/p) disorder. In: Companion of the 2018 ACM/IEEE International Conference on Human-Robot Interaction, pp. 359–360 (2018)
  * (32) Rivas, E.Q., Molina, E.S.: A proposal for a virtual world that supports theraphy of dyslalia. In: Proceedings of the 6th Euro American Conference on Telematics and Information Systems, pp. 371–374 (2012)
  * (33) Shneiderman, B.: Human-centered artificial intelligence: Reliable, safe & trustworthy. International Journal of Human–Computer Interaction 36(6), 495–504 (2020)
  * (34) Anjos, I., Grilo, M., Ascensão, M., Guimarães, I., Magalhães, J., Cavaco, S.: A serious mobile game with visual feedback for training sibilant consonants. In: International Conference on Advances in Computer Entertainment, pp. 430–450 (2017). Springer
  * (35) Benzeghiba, M., De Mori, R., Deroo, O., Dupont, S., Erbes, T., Jouvet, D., Fissore, L., Laface, P., Mertins, A., Ris, C., et al.: Automatic speech recognition and speech variability: A review. Speech communication 49(10-11), 763–786 (2007)
  * (36) Sheridan, T.B., Verplank, W.L.: Human and computer control of undersea teleoperators. Technical report, Massachusetts Inst of Tech Cambridge Man-Machine Systems Lab (1978)


Ensoul, which use existential feedback loops may be considered a sort of
implementable philosophical model, one in which this philosophical story might
be better understood. Stories represent our subjective beliefs about what is
happening in reality and as such the stories that we tell ourselves guide what
we do in both life and science. Thus, while it is important to acknowledge
that these stories are not equivalent to reality, these stories, should we
believe them, are equally important, considering the power that these stories
have over the sorts of actions that we take in the world. Interestingly, the
word “psychology” was originally defined as “the study of souls” before
becoming more commonly recognized as the “study of minds”. Indeed, the word
“psychology” is made from the combination of the Greek words “psychē “
(meaning “breath, principle of life, life, soul”), and ”logia” ( meaning
“speech, word, reason”). One of the aims of Ensoul is to take seriously the
idea that some of the properties one studies in psychology, like intelligence
and cognition, are not just present in the human mind, but in all “things”, or
SOULS. As such, methods and ideas from psychology such as PCT and
reinforcement learning can be useful in understanding the nature of any
“thing” independent of what that “thing” is made up of. This might suggest an
extension, or reinterpretation, of psychology that one might call
“neopsychology”, or the “new study of the SOULS”, where what we are primarily
interested in are these measurable substrate-invariant operationally defined
properties of any “thing” (i.e. intelligence, cognition, stress level, etc)
and how they scale up, or in what cases, if any, certain properties can be
said to "emerge". Since this paper primarily takes a modeling, or construction
approach to understanding SOULS, the framework has been named “Ensoul” which
is a verb meaning “to endow with a soul”.

## References

  * [1] Manipulating belief in free will and its downstream consequences: A meta-analysis.  2022\.
  * [2] Stephen Adams, Tyler Cody, and Peter A. Beling.  A survey of inverse reinforcement learning.  Artificial Intelligence Review, 55(6):4307–4346, February 2022\.
  * [3] Subutai Ahmad and Jeff Hawkins.  Properties of sparse distributed representations and their application to hierarchical temporal memory.  2015\.
  * [4] Neal G. Anderson and Gualtiero Piccinini.  Pancomputationalism and the computational description of physical systems.  February 2017.
  * [5] Saurabh Arora and Prashant Doshi.  A survey of inverse reinforcement learning: Challenges, methods and progress.  Artificial Intelligence, 297:103500, August 2021.
  * [6] Douglas J. Blackiston and Michael Levin.  Ectopic eyes outside the head in xenopus tadpoles provide sensory data for light-mediated learning.  Journal of Experimental Biology, 216(6):1031–1040, March 2013.
  * [7] Seville Chapman.  Catching a baseball.  American Journal of Physics, 36(10):868–870, October 1968.
  * [8] Brook T. Chernet, Chris Fields, and Michael Levin.  Long-range gap junctional signaling controls oncogene-mediated tumorigenesis in xenopus laevis embryos.  Frontiers in Physiology, 5, January 2015.
  * [9] Tom Conte, Erik DeBenedictis, Natesh Ganesh, Todd Hylton, John Paul Strachan, R. Stanley Williams, Alexander Alemi, Lee Altenberg, Gavin Crooks, James Crutchfield, Lidia del Rio, Josh Deutsch, Michael DeWeese, Khari Douglas, Massimiliano Esposito, Michael Frank, Robert Fry, Peter Harsha, Mark Hill, Christopher Kello, Jeff Krichmar, Suhas Kumar, Shih-Chii Liu, Seth Lloyd, Matteo Marsili, Ilya Nemenman, Alex Nugent, Norman Packard, Dana Randall, Peter Sadowski, Narayana Santhanam, Robert Shaw, Adam Stieg, Elan Stopnitzky, Christof Teuscher, Chris Watkins, David Wolpert, Joshua Yang, and Yan Yufik.  Thermodynamic computing.  2019\.
  * [10] Jamie Davies and Michael Levin.  Synthetic morphology via active and agential matter.  June 2022.
  * [11] Thomas Doctor, Olaf Witkowski, Elizaveta Solomonova, Bill Duane, and Michael Levin.  Biology, buddhism, and AI: Care as the driver of intelligence.  Entropy, 24(5):710, May 2022.
  * [12] Chris Fields, Karl Friston, James F. Glazebrook, and Michael Levin.  A free energy principle for generic quantum systems.  Progress in Biophysics and Molecular Biology, 173:36–59, September 2022.
  * [13] Chris Fields and Michael Levin.  Regulative development as a model for origin of life and artificial life studies.  October 2022.
  * [14] Steven A Frank.  Input-output relations in biological systems: measurement, information and the hill equation.  Biology Direct, 8(1), December 2013.
  * [15] Karl Friston, Lancelot Da Costa, Noor Sajid, Conor Heins, Kai Ueltzhöffer, Grigorios A. Pavliotis, and Thomas Parr.  The free energy principle made simpler but not too simple.  2022\.
  * [16] Mandi Gandelman, Mark Levy, Patricia Cassina, Luis Barbeito, and Joseph S. Beckman.  P2x7 receptor-induced death of motor neurons by a peroxynitrite/FAS-dependent pathway.  Journal of Neurochemistry, 126(3):382–388, June 2013.
  * [17] Stephen Grossberg.  Competition, decision, and consensus.  Journal of Mathematical Analysis and Applications, 66(2):470–493, November 1978.
  * [18] Stephen Grossberg.  Biological competition: Decision rules, pattern formation, and oscillations.  Proceedings of the National Academy of Sciences, 77(4):2338–2342, April 1980.
  * [19] Stephen Grossberg.  Behavioral economics and neuroeconomics: Cooperation, competition, preference, and decision making.  In The 2013 International Joint Conference on Neural Networks (IJCNN). IEEE, August 2013.
  * [20] Julia J. Harris, Renaud Jolivet, and David Attwell.  Synaptic energy use and supply.  Neuron, 75(5):762–777, September 2012.
  * [21] Donald D. Hoffman, Manish Singh, and Chetan Prakash.  The interface theory of perception.  Psychonomic Bulletin I& Review, 22(6):1480–1506, September 2015\.
  * [22] Jakob Hohwy.  The self-evidencing brain.  Noûs, 50(2):259–285, March 2014.
  * [23] Jacek Izydorczyk.  Three steps to the thermal noise death of moore’s law.  IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 18(1):161–165, January 2010.
  * [24] Kuno Kim, Shivam Garg, Kirankumar Shiragur, and Stefano Ermon.  Reward identification in inverse reinforcement learning.  139:5496–5505, 18–24 Jul 2021.
  * [25] Michael D. Kirchhoff and Tom Froese.  Where there is life there is mind: In support of a strong life-mind continuity thesis.  Entropy, 19(4):169, April 2017.
  * [26] Laszlo B Kish.  End of moore’s law: thermal (noise) death of integration in micro and nano electronics.  Physics Letters A, 305(3-4):144–149, December 2002.
  * [27] Joel Lehman, Jonathan Gordon, Shawn Jain, Kamal Ndousse, Cathy Yeh, and Kenneth O. Stanley.  Evolution through large models.  2022\.
  * [28] Joel Lehman and Kenneth O. Stanley.  Abandoning objectives: Evolution through the search for novelty alone.  Evolutionary Computation, 19(2):189–223, June 2011.
  * [29] Michael Levin.  The computational boundary of a “self”: Developmental bioelectricity drives multicellularity and scale-free cognition.  Frontiers in Psychology, 10, December 2019.
  * [30] Michael Levin.  Technological approach to mind everywhere: An experimentally-grounded framework for understanding diverse bodies and minds.  Frontiers in Systems Neuroscience, 16, March 2022.
  * [31] Michael Levin and Christopher J. Martyniuk.  The bioelectric code: An ancient computational medium for dynamic control of growth and form.  Biosystems, 164:76–93, February 2018.
  * [32] Warren Mansell, editor.  The interdisciplinary handbook of perceptual control theory the interdisciplinary handbook of perceptual control theory.  Academic Press, San Diego, CA, May 2020.
  * [33] Richard Marken, Richard Kennaway, and Tauseef Gulrez.  Behavioral illusions: The snark is a boojum.  Theory I& Psychology, 32(3):491–514, January 2022.
  * [34] Richard S. Marken and Dennis M. Shaffer.  The power law of movement: an example of a behavioral illusion.  Experimental Brain Research, 235(6):1835–1842, March 2017.
  * [35] Stuart M. Marshall, Cole Mathis, Emma Carrick, Graham Keenan, Geoffrey J. T. Cooper, Heather Graham, Matthew Craven, Piotr S. Gromski, Douglas G. Moore, Sara. I. Walker, and Leroy Cronin.  Identifying molecules as biosignatures with assembly theory and mass spectrometry.  Nature Communications, 12(1), May 2021.
  * [36] Stuart M. Marshall, Douglas G. Moore, Alastair R. G. Murray, Sara I. Walker, and Leroy Cronin.  Formalising the pathways to life using assembly spaces.  Entropy, 24(7):884, June 2022.
  * [37] Stuart M. Marshall, Douglas G. Moore, Alastair R. G. Murray, Sara I. Walker, and Leroy Cronin.  Formalising the pathways to life using assembly spaces.  Entropy, 24(7):884, June 2022.
  * [38] T. H. Morgan.  Experimental studies of the regeneration of planaria maculata.  Archiv für Entwicklungsmechanik der Organismen, 7(2-3):364–397, October 1898.
  * [39] Jeremy E Niven.  Neuronal energy consumption: biophysics, efficiency and evolution.  Current Opinion in Neurobiology, 41:129–135, December 2016.
  * [40] Graham Oddie.  Armstrong on the eleatic principle and abstract entities.  Philosophical Studies, 41(2):285–295, March 1982.
  * [41] Vaibhav P. Pai, Sherry Aw, Tal Shomrat, Joan M. Lemire, and Michael Levin.  Transmembrane voltage potential controls embryonic eye patterning in xenopus laevis.  Development, 139(2):313–323, January 2012.
  * [42] Mauricio H. Pontes, Anastasia Sevostyanova, and Eduardo A. Groisman.  When too much ATP is bad for protein synthesis.  Journal of Molecular Biology, 427(16):2586–2594, August 2015.
  * [43] William T. Powers.  Quantitative analysis of purposive systems: Some spadework at the foundations of scientific psychology.  Psychological Review, 85(5):417–435, September 1978.
  * [44] William T Powers.  Behavior: The Control Of Perception.  Benchmark Publications, 2 edition, March 2005.
  * [45] Michiel W. H. Remme, John Rinzel, and Susanne Schreiber.  Function and energy consumption constrain neuronal biophysics in a canonical computation: Coincidence detection.  PLOS Computational Biology, 14(12):e1006612, December 2018.
  * [46] E.D. Schneider and J.J. Kay.  Life as a manifestation of the second law of thermodynamics.  Mathematical and Computer Modelling, 19(6-8):25–48, March 1994\.
  * [47] Erwin Schrodinger.  What is life?: With mind and matter and autobiographical sketches.  June 2013.
  * [48] Abhishek Sharma, Dániel Czégel, Michael Lachmann, Christopher P. Kempes, Sara I. Walker, and Leroy Cronin.  Assembly theory explains and quantifies the emergence of selection and evolution.  2022\.
  * [49] Lakshwin Shreesha and Michael Levin.  Competency of the developmental layer alters evolutionary dynamics in an artificial embryogeny model of morphogenesis, 2022.
  * [50] L. Soros and Kenneth Stanley.  Identifying Necessary Conditions for Open-Ended Evolution through the Artificial Life World of Chromaria.  ALIFE 14: The Fourteenth International Conference on the Synthesis and Simulation of Living Systems:793–800, 07 2014.
  * [51] N. Stepp and M.T. Turvey.  On strong anticipation.  Cognitive Systems Research, 11(2):148–164, June 2010.
  * [52] Richard C Tolman.  Relativity, thermodynamics and cosmology.  Dover Books on Physics. Dover Publications, Mineola, NY, March 2003.
  * [53] Jan Toman and Jaroslav Flegr.  Stability-based sorting: The forgotten process behind (not only) biological evolution.  Journal of Theoretical Biology, 435:29–41, December 2017.
  * [54] Henry Veatch.  Aspects of scientific explanation and other essays in the philosophy of science.  Philosophy of Science, 37(2):312–314, June 1970.
  * [55] Rui Wang, Joel Lehman, Aditya Rawal, Jiale Zhi, Yulun Li, Jeff Clune, and Kenneth O. Stanley.  Enhanced poet: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions.  2020\.
  * [56] Stephen Wolfram.  A class of models with the potential to represent fundamental physics.  2020\.
  * [57] M V Zamaraeva, R Z Sabirov, E Maeno, Y Ando-Akatsuka, S V Bessonova, and Y Okada.  Cells die with increased cytosolic ATP during apoptosis: a bioluminescence study with intracellular luciferase.  Cell Death I& Differentiation, 12(11):1390–1397, May 2005.

##

##

##

##

## Glossary

  * •

Assembly Theory \- A physical theory of life which allows one to categorize
and detect life through measurement and application of a recursive algorithm.
The theory places different life forms on a spectrum of complexity.

  * •

Axis of persuadability \- the notion that every “thing” lies on a continuum
with respect to the amount of effort it takes to control that thing. The
amount of effort required is inversely proportional to the complexity/size of
the “things” cognitive light cone.

  * •

Cognition \- Operationally defined in this paper as the degree to which a
“thing” can “sense”, “believe” and “act”. In other words, the complexity
associated

  * •

Cognitive Capacity Tests \- Describes a suite of tests used to determine the
cognitive light cone of any “thing”. Some tests include: Test for controlled
variable (TCV), test for variable controllability (TVC), and test for control
switch (TCS).

  * •

Cognitive Light Cone \- describes how far in space and time an event can be
and still have an affect on the computations being enacted by some system.

  * •

Enerstatic Loop \- Short for “Energy Homeostatic Loop”, which is an
abstraction of a control system that learns to regulate its own “energy
level”, or particular dynamics, through the modification of its own structure.
It maps onto the idea of an adaptive thermodynamically open system, or
adaptive dissipative structure. Enerstatic loops represent “relationships”
between “structures”

  * •

Ensoul \- Acronym for “Enerstatic Network approach to Self Organizing
intelligent Ultra Low Power Systems”, a framework that this paper proposes in
order to better understand the nature of reality.

  * •

Environmental Enerstatic Loop (EEL) \- Short for “Environmental Enerstatic
Loop”, which is an abstraction utilized to implement energetically closed
systems. The EEL is responsible for creating structures and enerstatic loops.

  * •

Feedback \- The degree to which a thing’s effect, or “output”, affects its
cause, or “input”

  * •

Framework \- A framework is a set of rules, ideas, or beliefs that you employ
in order to solve problems or make decisions.

  * •

Free Energy Principle \- A mathematical formalization of the properties that
any self-organizing system must have.

  * •

Goal \- The desired result of a thing’s behavior (i.e. causal power).

  * •

Intelligence \- Operationally defined in this paper as the adaptive capacity
of a “thing” to meet its “goal” of existence.

  * •

Life-Mind Continuity Thesis \- The philosophical idea that life and mind
emerged simultaneously and have since then manifested themselves in
increasingly complex ways.

  * •

Neopsychologist \- “the new study of SOULS” - potential term for one who uses
the framework and approaches written in this paper. Specifically, one who is
primarily interested in studying measurable substrate-invariant operationally
defined properties of any “thing” (i.e. intelligence, cognition, stress level,
etc).

  * •

Open ended evolution \- The process through which new “things'' are generated
for a seemingly indefinite period of time. This process is believed to be
embodied by our universe and is well described by assembly theory.

  * •

Pancomputationalism - The metaphysical idea that every “thing” that exists can
be understood as “computing” something.

  * •

Self \- A collection of parts that share degrees of stress

  * •

Self-Evidencing \- The verb form of “self-evident”; an explanation is self-
evidencing if the event which it explains provides key evidence for the
explanation. What any “thing” does provides key evidence for its own existence
via an existential feedback loop.

  * •

SOULS \- Acronym for “Self Organizing intelligent Ultra Low Power System(s)”
meant to capture the multi-scale substrate independent nature of “things” that
Ensoul focuses on understanding and utilizing to create novel technologies.

  * •

Stress \- Any effect that pushes a “thing” away from its “preferred”, or
“healthy”, state.

  * •

Substance Monism - The metaphysical idea that every “thing” is made up of the
same sort of “stuff”

  * •

IOS \- Acronym for “Input Output System(s)” meant to capture SOULS whose
“fluctuations”, or, goal-directed behavior, have been squelched.

  * •

TAME \- Acronym for “Technological Approach to Mind Everywhere” a framework
developed by Michael Levin to understand diverse bodies and minds.

  * •

Teleology \- Purposeful, or goal directed, behavior.

  * •

Teleonomy \- Behavior that is not truly goal directed, but looks “as if” it
is.

  * •

von-Neumann architecture \- A computer architecture based on a 1945
description by John von Neumann. This is the architecture that most computers
today are based on. It has evolved to mean any “stored-program computer” in
which an instruction fetch and a data operation cannot occur at the same time.


during the execution of 3 on $Q^{\prime}$. Then, the guards placed on the
parents see not only $y$, but also see all other such vertices $y^{\prime}$
visible from $g$ (see Figure 29) due to cross-visibility across two adjacent
weak visibility polygons in the partition hierarchy $W$. So, this amounts to
choosing an extra primary vertex in $Q$, and thus the number of primary
vertices visible from $g\in Q^{U}_{opt}$ also increases by at most 1. Since
there could be at most one extra primary corresponding to every $g\in
G^{U}_{opt}$, for counting purposes, we can attribute these to $Q_{U}$ as an
extra primary vertex. So, $|Z|\leq 2\cdot|G_{opt}|$ is replaced by $|Z|\leq
3\cdot|G_{opt}|$ in our bound for all such $Q_{U}=V_{i,j}$. We have the
following results.

######  Theorem 47.

Let $P$ be a simple polygon of $n$ vertices. Then, a vertex guard set $S$ for
guarding all vertices of $P$ can be computed in $\mathcal{O}(n^{4})$ time, and
$|S|\leq 18\times|G_{opt}|$, where $G_{opt}$ is a an optimal vertex guard
cover for all vertices of $P$.

######  Theorem 48.

Let $P$ be a simple polygon of $n$ vertices. Then, a vertex guard set $S$ for
guarding the entire boundary of $P$ can be computed in $\mathcal{O}(n^{5})$
time, and $|S|\leq 18\times|G_{opt}|$, where $G_{opt}$ is a an optimal vertex
guard cover for the entire boundary of $P$.

######  Theorem 49.

Let $P$ be a simple polygon of $n$ vertices. Then, a vertex guard set $S$ for
guarding interior and boundary points of $P$ can be computed in
$\mathcal{O}(n^{5})$ time, and $|S|\leq 27\times|G_{opt}|$, where $G_{opt}$ is
a an optimal vertex guard cover for the entire interior and boundary of $P$.

##  7 Algorithms for Polygon Guarding using Edge Guards

Let us consider a slightly different version of the art gallery problem, where
edge guards rather than vertex guards are used for guarding a simple $n$-sided
polygon $P$. The hierarchical partitioning method used is almost exactly the
same as Algorithm 1 (presented in Section 3), where we guard the polygon using
vertex guards. While using edge guards instead, the only modification to
Algorithm 1 is that now we initially choose an arbitrary edge $v_{1}v_{2}$
instead of a vertex, and compute $V_{1,1}=\mathcal{VP}(v_{1}v_{2})$ (compare
with Lines 1-2 of Algorithm 1). As before, each weak visibility polygon in the
hierarchy is used to generate one weak visibility polygon in the next level
corresponding to each of its constructed edges.

As discussed in Section 5, let $Q$ denote a simple polygon that is weakly
visible from an internal chord $uv$, i.e. we have $\mathcal{VP}(uv)=Q$, and
observe that the chord $uv$ similarly splits $Q$ into two sub-polygons $Q_{U}$
and $Q_{L}$. Suppose we wish to guard an arbitrary vertex $z$ of $Q_{U}$ using
an edge guard. Then, a guard must be placed at an edge of $Q$ that belongs
fully or even partially to $\mathcal{VP}(z)$. Henceforth, let
$\mathcal{EVP}(z)$ denote the set of all polygonal edges that contain at least
one point belonging to $\mathcal{VP}(z)$. Further, let us define the _inward
visible edges_ and the _outward visible edges_ of $z$, denoted by
$\mathcal{EVP}^{+}(z)$ and $\mathcal{EVP}^{-}(z)$ respectively, as follows.

$\mathcal{EVP}^{+}(z)=\\{e\in\mathcal{EVP}(z)$: for any point $x\in e$, the
segment $zx$ does not intersect $uv$}

$\mathcal{EVP}^{-}(z)=\\{e\in\mathcal{EVP}(z)$ : for any point $x\in e$, the
segment $zx$ intersects $uv$}

We shall henceforth refer to the vertex guards belonging to
$\mathcal{EVP}^{+}(z)$ and $\mathcal{EVP}^{-}(z)$ as _inside guards_ and
_outside guards_ for $z$ respectively.

Observe that, for any vertex $z_{k}\in Z$, both $\mathcal{EVP}^{+}(z_{k})$ and
$\mathcal{EVP}^{-}(z_{k})$ may be considered to be ordered sets by taking into
account the natural ordering of the visible edges of $Q$ in clockwise order
along $bd_{c}(u,v)$ and in counter-clockwise order along $bd_{cc}(u,v)$
respectively. Let us denote the _first visible edge_ and the _last visible
edge_ belonging to the ordered set $\mathcal{EVP}^{-}(z_{k})$ by $f(z_{k})$
and $l(z_{k})$ respectively (see Figure 9). Also, we denote by
$l^{\prime}(z_{k})$ the _last visible point_ from $z_{k}$, which is obtained
by extending the ray $\overrightarrow{z_{k}p(v,z_{k})}$ till it touches
$bd_{cc}(u,v)$.

As in Section 5, our algorithm selects a subset $Z$ of vertices of $Q_{U}$,
and places a fixed number of both inside and outside edge guards corresponding
to each of them, so that these edge guards together see the entire $Q_{U}$. As
before, we refer to this subset of special vertices as _primary vertices_ ,
and denote it by $Z$. Moreover, the choice of primary vertices is also made in
a manner identical to that discussed in Section 5.

Once again, a natural idea is to place outside edge guards in a greedy manner
so that they lie in the common intersection of outward visible edges of as
many vertices of $Q_{U}$ as possible. For any primary vertex $z_{k}$, let us
denote by $\mathcal{OEV}^{-}(z_{k})$ the set of unmarked vertices of $Q_{U}$
whose outward visible edges overlap with those of $z_{k}$. In other words,

$\mathcal{OEV}^{-}(z_{k})=\\{x\in\mathcal{V}(Q_{U}):\mbox{ $x$ is unmarked,
and }\mathcal{EVP}^{-}(z_{k})\cap\mathcal{EVP}^{-}(x)\neq\emptyset\\}$

So, each vertex of $Q_{U}$ belonging to $\mathcal{OEV}^{-}(z_{k})$ is visible
from at least one edge of $\mathcal{EVP}^{-}(z_{k})$. Further,
$\mathcal{OEV}^{-}(z_{k})$ can be considered to be an ordered set, where for
any pair of elements $x_{1},x_{2}\in\mathcal{OEV}^{-}(z_{k})$, we define
$x_{1}\prec x_{2}$ if and only if $l^{\prime}(x_{1})$ precedes
$l^{\prime}(x_{2})$ in counter-clockwise order on $bd_{cc}(u,v)$. For the
current primary vertex $z_{k}$, let us assume without loss of generality that
$\mathcal{OEV}^{-}(z_{k})=\\{x^{k}_{1},x^{k}_{2},x^{k}_{3},\dots\,x^{k}_{m(k)}\\}$
such that $l^{\prime}(x^{k}_{1})\prec l^{\prime}(x^{k}_{2})\prec\dots\prec
l^{\prime}(x^{k}_{m(k)})$ in counter-clockwise order on $bd_{cc}(u,v)$.

Just as we partitioned $\mathcal{OVV}^{-}(z_{k})$ while guarding the polygon
using vertex guards, let us partition the vertices belonging to
$\mathcal{OEV}^{-}(z_{k})$ into 3 sets, viz. $A^{k}$, $B^{k}$ and $C^{k}$, in
the following manner. Consider any vertex
$x^{k}_{i}\in\mathcal{OEV}^{-}(z_{k})$, such that
$\mathcal{EVP}^{-}(x^{k}_{i})$ creates a constructed edge
$t(x^{k}_{i})t^{\prime}(x^{k}_{i})$, where $t(x^{k}_{i})\in\mathcal{V}(Q_{L})$
is a polygonal vertex and $t^{\prime}(x^{k}_{i})$ is the point where
$\overrightarrow{x^{k}_{i}t(x^{k}_{i})}$ first intersects $bd_{cc}(u,v)$.
Every vertex of $\mathcal{OEV}^{-}(z_{k})$ visible from $l(z_{k})$ is included
in $B^{k}$. Observe that, by definition $z^{k}\in B^{k}$. Obviously, for each
vertex $x^{k}_{i}\in\mathcal{OEV}^{-}(z_{k})\setminus B^{k}$, $x^{k}_{i}$ is
not visible from $l(z_{k})$ due to the presence of some constructed edge. The
vertices of $\mathcal{OEV}^{-}(z_{k})\setminus B^{k}$ are categorized into
$A^{k}$ and $C^{k}$ based on whether this constructed edge creates a right
pocket or a left pocket. Suppose
$x^{k}_{i}\in\mathcal{OEV}^{-}(z_{k})\setminus B^{k}$ is a vertex such that
$\mathcal{VP}(x^{k}_{i})$ creates a constructed edge
$t(x^{k}_{i})t^{\prime}(x^{k}_{i})$, where $t(x^{k}_{i})\in\mathcal{V}(Q_{L})$
is a polygonal vertex and $t^{\prime}(x^{k}_{i})$ is the point where
$\overrightarrow{x^{k}_{i}t(x^{k}_{i})}$ first intersects $bd_{cc}(u,v)$. If
$t(x^{k}_{i})$ lies on $bd_{cc}(f^{\prime}(z_{k}),l^{\prime}(z_{k}))$ and
$t^{\prime}(x^{k}_{i})$ lies on $bd_{cc}(l(z_{k}),v)$, i.e. if $f(z_{k})\prec
t(x^{k}_{i})\prec l^{\prime}(z_{k})$ and $l(z_{k})\prec
t^{\prime}(x^{k}_{i})\prec v$, then $x^{k}_{i}$ is included in $A^{k}$. For
instance, in Figure 11, $x_{1}^{2}\in A^{2}$ due to the constructed edge
$t(x_{1}^{2})t^{\prime}(x_{1}^{2})$. On the other hand, if $t(x^{k}_{i})$ lies
on $bd_{cc}(l^{\prime}(z_{k}),v)$ and $t^{\prime}(x^{k}_{i})$ lies on
$bd_{cc}(f(z_{k}),l^{\prime}(z_{k}))$, i.e. if $l^{\prime}(z_{k})\prec
t(x^{k}_{i})\prec v$ and $f(z_{k})\prec t^{\prime}(x^{k}_{i})\prec
l^{\prime}(z_{k})$, then $x^{k}_{i}$ is included in $C^{k}$. For instance, in
Figure 11, $x_{3}^{2}\in C^{2}$ due to the constructed edge
$t(x_{3}^{2})t^{\prime}(x_{3}^{2})$. Observe that, all vertices of $A^{k}$
must lie on $bd_{c}(u,z_{k})$, whereas all vertices of $C^{k}$ must lie on
$bd_{c}(z_{k},v)$. We have the following lemma, whose proof is similar to the
proof of Lemma 4.

######  Lemma 50.

The edge $l(z_{k})$ sees all vertices belonging to $B^{k}$.

Depending on the vertices in $A^{k}$, $B^{k}$ and $C^{k}$, we have the
following cases, just as in Section 5.3.

Case 1 -

$\mathcal{CI}(A^{k}\cup B^{k}\cup C^{k})\neq\emptyset$ (see Figure 11)

Case 2 -

$\mathcal{CI}(A^{k}\cup B^{k}\cup C^{k})=\emptyset$ and
$\mathcal{CI}(B^{k})\neq\emptyset$

Case 2a -

$\mathcal{CI}(A^{k})\neq\emptyset$ and $\mathcal{CI}(C^{k})\neq\emptyset$ (see
Figure 12)

Case 2b -

$\mathcal{CI}(A^{k})=\emptyset$ and $\mathcal{CI}(C^{k})\neq\emptyset$ (see
Figure 13)

Case 2c -

$\mathcal{CI}(A^{k})\neq\emptyset$ and $\mathcal{CI}(C^{k})=\emptyset$ (see
Figure 14)

Case 2d -

$\mathcal{CI}(A^{k})=\emptyset$ and $\mathcal{CI}(C^{k})=\emptyset$ (see
Figure 15)

In each of the above cases, we also proceed to choose the three outside edge
guards $s^{k}_{1}$, $s^{k}_{2}$ and $s^{k}_{3}$ in a similar manner as was
done in Section 5.3, with the only difference being that here we use the new
definitions of $\mathcal{EVP}(z_{k})$ and $\mathcal{OEV}(z_{k})$ instead of
$\mathcal{VVP}(z_{k})$ and $\mathcal{OVV}(z_{k})$ respectively. To elaborate
further, we choose the edge guard $s_{3}^{k}=l(z_{k})$; if the guards
$s^{k}_{1}$ and $s^{k}_{2}$ are chosen from a common intersection region, then
we use $\mathcal{EVP}^{-}(z_{k})$ rather than $\mathcal{VVP}^{-}(z_{k})$; if
the guards $s^{k}_{1}$ and $s^{k}_{2}$ are chosen greedily, then we use the
last edge along the traversal after which some vertex belonging to $A^{k}$ and
$C^{k}$ respectively is no longer visible. We can establish lemmas similar to
Lemmas 8 to 35 (in Section 5.3) from these choices of edge guards.

As far as the choice of inside edge guards is concerned, we again choose them
following the same case analysis (see Figures 23, 25 and 25) as described in
Section 5.4. To elaborate further, we choose the edge guards $s^{k}_{4}$ and
$s^{k}_{5}$ to be the edges adjacent to $p(u,z_{k})$ and $p(v,z_{k})$
respectively that lie on $bd_{c}(p(u,z_{k}),p(v,z_{k}))$, whereas for the
greedily chosen guard $s^{k}_{6}$ (if required at all) we use the last edge
along the traversal after which some vertex belonging to
$\mathcal{OEV}^{+}(z_{k})$ is no longer visible. Again, we can establish
lemmas similar to Lemmas 37 to 40 (in Section 5.4) from these choices of edge
guards. As a consequence, we obtain the following theorems.

######  Theorem 51.

Let $Z$ be the set of primary vertices chosen by our modified algorithm, and
let $S$ be the set of all edge guards placed by it. Then, $|S|\leq
6\cdot|Z|\leq 12\cdot|G_{opt}|$.

######  Theorem 52.

It is possible to compute in $\mathcal{O}(n^{4})$ time a set of inside and
outside edge guards for guarding all vertices of a weak visibility polygon
$Q_{U}$ such that the number of edge guards chosen is at most
$12\cdot|G_{opt}|$, where $G_{opt}$ is an optimal edge guard cover for all
vertices of $Q_{U}$.

In Theorem 52, we established the existence of an approximation algorithm for
guarding a polygon $Q$ weakly visible from a chord $uv$. If this same
algorithm is executed on the union of overlapping weak visibility polygons
$Q$, then it chooses primary vertices in the same way irrespective of chords
in $Q$, thereby producing a set of edge guards that sees the entire union $Q$.
So, if this algorithm is used for every overlapping weak visibility polygon in
$P$, then the entire polygon $P$ can be guarded by the union of the guard sets
produced for guarding these overlapping weak visibility polygons. Note that
there is no increase in running time for this overall algorithm. Moreover,
since each vertex can appear in at most two weak visibility polygons from the
hierarchy $W$, we obtain the following theorem.

######  Theorem 53.

Let $P$ be a simple polygon having $n$ vertices. Then, an edge guard set $S$
for guarding all vertices of $P$ can be computed in $\mathcal{O}(n^{4})$ time,
such that $|S|\leq 18\times|G_{opt}|$, where $G_{opt}$ is an optimal edge
guard cover for all vertices of $P$.

However, it may not always be true that the guards in $S$ see all interior
points of $Q_{U}$. Consider the polygon shown in Figure 31. Assume that our
previous algorithms places guards at $s_{4}^{k}$ and $s_{5}^{k}$, and all
vertices of $bd_{c}(p(u,z_{k}),p(v,z_{k}))$ become visible from $s_{4}^{k}$ or
$s_{5}^{k}$. However, the triangular region
$Q_{U}\setminus(VP(p(u,z_{k})))\cup VP(p(v,z_{k}))$, bounded by the segments
$x_{1}x_{2}$, $x_{2}x_{3}$ and $x_{3}x_{1}$, is not visible from $s_{4}^{k}$
or $s_{5}^{k}$. Also, one of the sides $x_{1}x_{2}$ of the triangle
$x_{1}x_{2}x_{3}$ is a part of the polygonal edge $a_{1}a_{2}$. In fact, for
any such region invisible from edge guards $s_{4}^{k},s_{5}^{k}\in S^{k}$
corresponding to some $z_{k}\in Z$, henceforth referred to as an _invisible
cell_ , one of the sides must always be a part of a polygonal edge. The
polygonal edge which contributes as a side to the invisible cell is referred
to as its corresponding _partially invisible edge_.

Observe that $s_{4}^{k}$ and $s_{5}^{k}$ can in fact create several invisible
cells, in a manner very similar to that shown in Figure 27. Each invisible
cell must be wholly contained within the intersection region (which is a
triangle) of a left pocket and a right pocket. For example, in Figure 31, the
invisible cell $x_{1}x_{2}x_{3}$ is actually the entire intersection region of
the left pocket of $VP(s_{4}^{k})$ and the right pocket of $VP(s_{5}^{k})$. In
general, where $VP(s_{4}^{k})$ has several left pockets and $VP(s_{5}^{k})$
has several right pockets which intersect pairwise to create multiple
invisible cells (as shown in Figure 27), every such cell can be seen by
placing guards on the common vertices between adjacent pairs of cells.
Further, if $G_{opt}$ is also constrained to guard these invisible cells using
only inward guards from $Q_{U}$, then the number of such additional guards
required can be at most twice of $G_{opt}$, as shown by Bhattacharya et al.
[4]. However, in the absence of any constraint on placing guards, $G_{opt}$
may place an outside guard in $Q_{L}$ that sees several such invisible cells.
So, it is natural to explore the possibility of being able to guard all such
invisible cells by using additional edge guards from $Q_{L}$, in combination
with guards from $Q_{U}$.

Just as in Section 5.5, we present a modified algorithm that ensures that all
partially invisible edges are guarded completely, and therefore the entire
$bd_{c}(u,v)$ is guarded. Let us compute the weak visibility polygons
corresponding to every edge of $P$. Then, the non-vertex endpoints of all the
constructed edges belonging to these weak visibility polygons partition the
boundary of $Q_{U}$ into distinct intervals called _minimal visible
intervals_. We have the following lemmas.

######  Lemma 54.

Every minimal visible interval on the boundary of $Q_{U}$ is either entirely
visible from an edge or totally not visible from that edge.

The modified algorithm first computes all minimal visible intervals and
chooses one internal representative point from each minimal visible interval
on the boundary of $Q_{U}$. These representative points are referred to as
_pseudo-vertices_. Alongside the original polygonal vertices of $Q$, all
pseudo-vertices are introduced on the boundary of $Q_{U}$, and the modified
polygon is denoted by $Q^{\prime}$. Note that the endpoints of minimal visible
intervals are not introduced in $Q^{\prime}$. In the modified algorithm, the
pseudo-vertices of $Q^{\prime}$ are treated in the same manner as the original
vertices. We compute $\mathcal{EVP}^{+}(z)$ and $\mathcal{EVP}^{-}(z)$ for all
vertices of $Q^{\prime}$, irrespective of whether it is a pseudo-vertex, and
some of the psuedo-vertices may even be chosen as primary vertices.

######  Theorem 55.

For the edge guard set $S$ computed by our modified algorithm with pseudo-
vertices, $|S|\leq 6\cdot|Z|\leq 12\cdot|G_{opt}|$, where $G_{opt}$ is an
optimal edge guard cover for the entire boundary of $Q_{U}$.

######  Theorem 56.

Let $P$ be a simple polygon having $n$ vertices. Then, an edge guard set $S$
for guarding the entire boundary of $P$ can be computed in
$\mathcal{O}(n^{5})$ time, such that $|S|\leq 18\times|G_{opt}|$, where
$G_{opt}$ is an optimal edge guard cover for the entire boundary of $P$.

###### Proof.

This result follows directly from Theorem 55. The running time bound of
$\mathcal{O}(n^{5})$ can be established through arguments very similar to
those in the proof of Theorem 45. The only difference lies in the computation
of $\mathcal{EVP}(z_{k})$ and $\mathcal{OEV}(z_{k})$, in place of
$\mathcal{VVP}(z_{k})$ and $\mathcal{OVV}(z_{k})$ respectively, for every
primary vertex $z_{k}\in Z$, but the time complexity of these computations are
also same. ∎

Figure 30:  All vertices are visible from edge guards $s^{k}_{4}$ or
$s^{k}_{5}$, but the triangle $x_{1}x_{2}x_{3}$ is invisible.

Figure 31:  Two outside edge guards $g$ and $g^{\prime}$ can create a residual
invisible cell that is a part of $x_{1}x_{2}x_{3}$.

However, there is no guarantee that $S$ sees the entire interior of $Q_{U}$,
as there may remain residual invisible cells in the interior of $Q_{U}$ (see
Figure 29). Consider a residual invisible cell that is a part of an invisible
cell $x_{1}x_{2}x_{3}$, where $x_{1}x_{2}$ is contained in a partially
invisible edge. For such a residual invisible cell, there exists a pseudo-
vertex on $x_{1}x_{2}$ whose parents can see the entire cell
$x_{1}x_{2}x_{3}$, as discussed earlier in the context of placing inside
guards for guarding entire visibility cell. So, placing a guard at an
appropriate parent, such as the parent $z_{k}$ for the pseudo-vertex that will
be placed on the minimal visible interval $x_{1}x_{2}$ in Figure 29,
guarantees that the residual invisible cell is totally visible. Since such an
additional inside guard on $Q_{U}$ corresponds to an unique outward guard in
$Q_{L}$, the additional number of inside guards can be at most the number of
outside guards. This amounts to placing at most (3+3)=6 inside guards and 3
outside guards corresponding to each primary vertex, while the number of
primary vertices chosen remains at most $2\cdot|G_{opt}|$. We summarize the
result in the following theorem.

######  Theorem 57.

Let $P$ be a simple polygon having $n$ vertices. Then, an edge guard set $S$
for guarding the entire interior and boundary points of $P$ can be computed in
$\mathcal{O}(n^{5})$ time, such that $|S|\leq 27\times|G_{opt}|$, where
$G_{opt}$ is a an optimal edge guard cover for the entire interior and
boundary of $P$.

##  8 Concluding Remarks

We have presented three approximation algorithms for guarding simple polygons
using vertex guards. We have also shown how these algorithms can be modified
to obtain similar approximation bounds while using edge guards. Though the
approximation ratios for our algorithms are slightly on the higher side, they
do successfully settle the long-standing conjecture by Ghosh by providing
constant-factor approximation algorithms for this problem. We feel that, in
practice, our algorithms will provide guard sets that are much closer in size
to an optimal solution. This can be further ensured by introducing a
redundancy check after the placement of each new guard, which removes each
(inside or outside) guard placed previously by the algorithm that does not see
at least one vertex of $Q_{U}$ not seen by any other guard placed so far. By
incorporating such a redundancy check, we conjecture that our analysis of the
approximation bound can be tightened further, and the existence of smaller
approximation ratios can be proven for these three variations of the polygon
guarding problem. Our algorithms exploit several deep visibility structures of
simple polygons which are interesting in their own right.

## References

  * [1] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow.  The art gallery problem is $\exists$R-complete.  CoRR, abs/1704.06969, 2017.
  * [2] Alok Aggarwal.  The art gallery theorem: its variations, applications and algorithmic aspects.  PhD thesis, The Johns Hopkins University, Baltimore, Maryland, 1984.
  * [3] Pritam Bhattacharya, Subir Kumar Ghosh, and Bodhayan Roy.  Vertex Guarding in Weak Visibility Polygons.  In Proceedings of the 1st International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2015), volume 8959 of Lecture Notes in Computer Science (LNCS), pages 45–57. Springer, 2015.
  * [4] Pritam Bhattacharya, Subir Kumar Ghosh, and Bodhayan Roy.  Approximability of guarding weak visibility polygons.  Discrete Applied Mathematics, 228:109 – 129, 2017.
  * [5] Édouard Bonnet and Tillmann Miltzow.  An Approximation Algorithm for the Art Gallery Problem.  In Boris Aronov and Matthew J. Katz, editors, 33rd International Symposium on Computational Geometry (SoCG 2017), volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [6] Václav Chvátal.  A combinatorial theorem in plane geometry.  Journal of Combinatorial Theory, Series B, 18(1):39–41, 1975.
  * [7] Ajay Deshpande, Taejung Kim, Erik D. Demaine, and Sanjay E. Sarma.  A pseudopolynomial time o(log n)-approximation algorithm for art gallery problems.  In WADS, pages 163–174, 2007.
  * [8] Alon Efrat and Sariel Har-Peled.  Guarding galleries and terrains.  Information Processing Letters, 100(6):238–245, 2006.
  * [9] Stephan Eidenbenz, Christoph Stamm, and Peter Widmayer.  Inapproximability of some art gallery problems.  Canadian Conference on Computational Geometry, pages 1–11, 1998\.
  * [10] Stephan Eidenbenz, Christoph Stamm, and Peter Widmayer.  Inapproximability results for guarding polygons and terrains.  Algorithmica, 31(1):79–113, 2001.
  * [11] Steve Fisk.  A short proof of Chvátal’s watchman theorem.  Journal of Combinatorial Theory, Series B, 24(3):374, 1978.
  * [12] Subir Kumar Ghosh.  Approximation algorithms for art gallery problems.  In Proceedings of Canadian Information Processing Society Congress, page 429–434. Canadian Information Processing Society, 1987.
  * [13] Subir Kumar Ghosh.  Visibility Algorithms in the Plane.  Cambridge University Press, 2007.
  * [14] Subir Kumar Ghosh.  Approximation algorithms for art gallery problems in polygons.  Discrete Applied Mathematics, 158(6):718–722, 2010.
  * [15] Subir Kumar Ghosh.  Approximation algorithms for art gallery problems in polygons and terrains.  WALCOM: Algorithms and Computation, pages 21–34, 2010.
  * [16] Subir Kumar Ghosh and David M. Mount.  An output-sensitive algorithm for computing visibility graphs.  SIAM Journal of Computing, 20(5):888–910, 1991.
  * [17] John Hershberger.  An optimal visibility graph algorithm for triangulated simple polygons.  Algorithmica, 4(1):141–155, 1989.
  * [18] J. Kahn, M. Klawe, and D. Kleitman.  Traditional galleries require fewer watchmen.  SIAM Journal of Algebraic and Discrete Methods, 4(2):194–206, 1983\.
  * [19] Matthew J Katz.  A PTAS for vertex guarding weakly-visible polygons.  arXiv preprint arXiv:1803.02160, 2018.
  * [20] Matthew J. Katz and Gabriel S. Roisman.  On guarding the vertices of rectilinear domains.  Computational Geometry, 39(3):219–228, 2008.
  * [21] James King and David G. Kirkpatrick.  Improved approximation for guarding simple galleries from the perimeter.  Discrete & Computational Geometry, 46(2):252–269, 2011.
  * [22] David G. Kirkpatrick.  An o(lg lg opt)-approximation algorithm for multi-guarding galleries.  Discrete & Computational Geometry, 53(2):327–343, 2015.
  * [23] Erik A Krohn and Bengt J Nilsson.  Approximate Guarding of Monotone and Rectilinear Polygons.  Algorithmica, 66:564–594, 2013.
  * [24] D.T. Lee and A. Lin.  Computational complexity of art gallery problems.  IEEE Transactions on Information Theory, 32(2):276–282, 1986.
  * [25] Joseph O’Rourke.  An alternative proof of the rectilinear art gallery theorem.  Journal of Geometry, 211:118–130, 1983.
  * [26] Joseph O’Rourke.  Art gallery theorems and algorithms.  Oxford University Press, London, 1987.
  * [27] Joseph O’Rourke and Kenneth J. Supowit.  Some NP-hard polygon decomposition problems.  IEEE Transactions on Information Theory, 29(2):181–189, 1983.
  * [28] Dietmar Schuchardt and Hans-Dietrich Hecker.  Two NP-Hard Art-Gallery Problems for Ortho-Polygons.  Mathematical Logic Quarterly, 41:261–267, 1995.
  * [29] Subhash Suri.  A linear time algorithm with minimum link paths inside a simple polygon.  Comput. Vision Graph. Image Process., 35(1):99–110, July 1986.
  * [30] Subhash Suri.  Minimum link paths in polygons and related problems.  PhD thesis, The Johns Hopkins University, Baltimore, Maryland, 1987.