Loading…
Guarding in a simple polygon
Guarding in a simple polygon was motivated by art gallery problems. A guard capable of moving along a line segment in a polygon is called a mobile guard. In this paper, we discuss about two different degrees of patrol freedom of mobile guards. First, a guard diagonal is an internal diagonal that a m...
Saved in:
| Published in: | Information processing letters 2000-09, Vol.75 (4), p.153-158 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c363t-31945b1c0619a5c29919d6910bc634c5221ff7467610c02950b55ff0d051f3d73 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c363t-31945b1c0619a5c29919d6910bc634c5221ff7467610c02950b55ff0d051f3d73 |
| container_end_page | 158 |
| container_issue | 4 |
| container_start_page | 153 |
| container_title | Information processing letters |
| container_volume | 75 |
| creator | Lu, Bor-Kuan Hsu, Fang-Rong Tang, Chuan Yi |
| description | Guarding in a simple polygon was motivated by art gallery problems. A guard capable of moving along a line segment in a polygon is called a
mobile guard. In this paper, we discuss about two different degrees of patrol freedom of mobile guards. First, a
guard diagonal is an internal diagonal that a mobile guard moving along the diagonal in a polygon and every interior point of the polygon can be seen by the mobile guard. Second, a
guard chord is an internal chord that a mobile guard moving along the chord in a polygon and every interior point of the polygon can be seen by the mobile guard. In this paper, we solve the problem of finding the longest guard diagonal in
O(n)
time, the shortest guard diagonal in
O(nα(n))
and the longest guard chord in
O(n)
time of a simple polygon
P
with
n vertices, where
α(n) is the inverse of Ackermann's function. |
| doi_str_mv | 10.1016/S0020-0190(00)00100-9 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_237280265</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0020019000001009</els_id><sourcerecordid>60684741</sourcerecordid><originalsourceid>FETCH-LOGICAL-c363t-31945b1c0619a5c29919d6910bc634c5221ff7467610c02950b55ff0d051f3d73</originalsourceid><addsrcrecordid>eNqFkEFLxDAQhYMoWFf_gUIRD3qoziRN2pxEFl2FBQ_qOWTTZMnSbWvSFfbf27qLHoWBuXzvvZlHyAXCLQKKuzcAChmghGuAGwAEyOQBSbAsaCYQ5SFJfpFjchLjCgBEzoqEnM82OlS-Waa-SXUa_bqrbdq19XbZNqfkyOk62rP9npCPp8f36XM2f529TB_mmWGC9RlDmfMFGhAoNTdUSpSVkAgLI1huOKXoXJGLQiAYoJLDgnPnoAKOjlUFm5DLnW8X2s-Njb1atZvQDJGKsoKWQAUfIL6DTGhjDNapLvi1DluFoMYe1E8PanxSwThDD0oOuqu9uY5G1y7oxvj4J87LvKTjDfc7zA6PfnkbVDTeNsZWPljTq6r1_wR9A7TWbQA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>237280265</pqid></control><display><type>article</type><title>Guarding in a simple polygon</title><source>ScienceDirect Freedom Collection 2022-2024</source><source>Backfile Package - Computer Science (Legacy) [YCS]</source><source>Backfile Package - Mathematics (Legacy) [YMT]</source><creator>Lu, Bor-Kuan ; Hsu, Fang-Rong ; Tang, Chuan Yi</creator><creatorcontrib>Lu, Bor-Kuan ; Hsu, Fang-Rong ; Tang, Chuan Yi</creatorcontrib><description>Guarding in a simple polygon was motivated by art gallery problems. A guard capable of moving along a line segment in a polygon is called a
mobile guard. In this paper, we discuss about two different degrees of patrol freedom of mobile guards. First, a
guard diagonal is an internal diagonal that a mobile guard moving along the diagonal in a polygon and every interior point of the polygon can be seen by the mobile guard. Second, a
guard chord is an internal chord that a mobile guard moving along the chord in a polygon and every interior point of the polygon can be seen by the mobile guard. In this paper, we solve the problem of finding the longest guard diagonal in
O(n)
time, the shortest guard diagonal in
O(nα(n))
and the longest guard chord in
O(n)
time of a simple polygon
P
with
n vertices, where
α(n) is the inverse of Ackermann's function.</description><identifier>ISSN: 0020-0190</identifier><identifier>EISSN: 1872-6119</identifier><identifier>DOI: 10.1016/S0020-0190(00)00100-9</identifier><identifier>CODEN: IFPLAT</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Algorithms ; Art galleries & museums ; Combinatorics ; Combinatorics. Ordered structures ; Exact sciences and technology ; Graph algorithms ; Graph theory ; Graphs ; Mathematics ; Optimization ; Sciences and techniques of general use ; Simple polygon ; Studies</subject><ispartof>Information processing letters, 2000-09, Vol.75 (4), p.153-158</ispartof><rights>2000 Elsevier Science B.V.</rights><rights>2000 INIST-CNRS</rights><rights>Copyright Elsevier Sequoia S.A. Sep 30, 2000</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c363t-31945b1c0619a5c29919d6910bc634c5221ff7467610c02950b55ff0d051f3d73</citedby><cites>FETCH-LOGICAL-c363t-31945b1c0619a5c29919d6910bc634c5221ff7467610c02950b55ff0d051f3d73</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.sciencedirect.com/science/article/pii/S0020019000001009$$EHTML$$P50$$Gelsevier$$H</linktohtml><link.rule.ids>314,780,784,3429,3564,27924,27925,45972,46003</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&idt=1484827$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Lu, Bor-Kuan</creatorcontrib><creatorcontrib>Hsu, Fang-Rong</creatorcontrib><creatorcontrib>Tang, Chuan Yi</creatorcontrib><title>Guarding in a simple polygon</title><title>Information processing letters</title><description>Guarding in a simple polygon was motivated by art gallery problems. A guard capable of moving along a line segment in a polygon is called a
mobile guard. In this paper, we discuss about two different degrees of patrol freedom of mobile guards. First, a
guard diagonal is an internal diagonal that a mobile guard moving along the diagonal in a polygon and every interior point of the polygon can be seen by the mobile guard. Second, a
guard chord is an internal chord that a mobile guard moving along the chord in a polygon and every interior point of the polygon can be seen by the mobile guard. In this paper, we solve the problem of finding the longest guard diagonal in
O(n)
time, the shortest guard diagonal in
O(nα(n))
and the longest guard chord in
O(n)
time of a simple polygon
P
with
n vertices, where
α(n) is the inverse of Ackermann's function.</description><subject>Algorithms</subject><subject>Art galleries & museums</subject><subject>Combinatorics</subject><subject>Combinatorics. Ordered structures</subject><subject>Exact sciences and technology</subject><subject>Graph algorithms</subject><subject>Graph theory</subject><subject>Graphs</subject><subject>Mathematics</subject><subject>Optimization</subject><subject>Sciences and techniques of general use</subject><subject>Simple polygon</subject><subject>Studies</subject><issn>0020-0190</issn><issn>1872-6119</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2000</creationdate><recordtype>article</recordtype><recordid>eNqFkEFLxDAQhYMoWFf_gUIRD3qoziRN2pxEFl2FBQ_qOWTTZMnSbWvSFfbf27qLHoWBuXzvvZlHyAXCLQKKuzcAChmghGuAGwAEyOQBSbAsaCYQ5SFJfpFjchLjCgBEzoqEnM82OlS-Waa-SXUa_bqrbdq19XbZNqfkyOk62rP9npCPp8f36XM2f529TB_mmWGC9RlDmfMFGhAoNTdUSpSVkAgLI1huOKXoXJGLQiAYoJLDgnPnoAKOjlUFm5DLnW8X2s-Njb1atZvQDJGKsoKWQAUfIL6DTGhjDNapLvi1DluFoMYe1E8PanxSwThDD0oOuqu9uY5G1y7oxvj4J87LvKTjDfc7zA6PfnkbVDTeNsZWPljTq6r1_wR9A7TWbQA</recordid><startdate>20000930</startdate><enddate>20000930</enddate><creator>Lu, Bor-Kuan</creator><creator>Hsu, Fang-Rong</creator><creator>Tang, Chuan Yi</creator><general>Elsevier B.V</general><general>Elsevier Science</general><general>Elsevier Sequoia S.A</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20000930</creationdate><title>Guarding in a simple polygon</title><author>Lu, Bor-Kuan ; Hsu, Fang-Rong ; Tang, Chuan Yi</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c363t-31945b1c0619a5c29919d6910bc634c5221ff7467610c02950b55ff0d051f3d73</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2000</creationdate><topic>Algorithms</topic><topic>Art galleries & museums</topic><topic>Combinatorics</topic><topic>Combinatorics. Ordered structures</topic><topic>Exact sciences and technology</topic><topic>Graph algorithms</topic><topic>Graph theory</topic><topic>Graphs</topic><topic>Mathematics</topic><topic>Optimization</topic><topic>Sciences and techniques of general use</topic><topic>Simple polygon</topic><topic>Studies</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Lu, Bor-Kuan</creatorcontrib><creatorcontrib>Hsu, Fang-Rong</creatorcontrib><creatorcontrib>Tang, Chuan Yi</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Information processing letters</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Lu, Bor-Kuan</au><au>Hsu, Fang-Rong</au><au>Tang, Chuan Yi</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Guarding in a simple polygon</atitle><jtitle>Information processing letters</jtitle><date>2000-09-30</date><risdate>2000</risdate><volume>75</volume><issue>4</issue><spage>153</spage><epage>158</epage><pages>153-158</pages><issn>0020-0190</issn><eissn>1872-6119</eissn><coden>IFPLAT</coden><abstract>Guarding in a simple polygon was motivated by art gallery problems. A guard capable of moving along a line segment in a polygon is called a
mobile guard. In this paper, we discuss about two different degrees of patrol freedom of mobile guards. First, a
guard diagonal is an internal diagonal that a mobile guard moving along the diagonal in a polygon and every interior point of the polygon can be seen by the mobile guard. Second, a
guard chord is an internal chord that a mobile guard moving along the chord in a polygon and every interior point of the polygon can be seen by the mobile guard. In this paper, we solve the problem of finding the longest guard diagonal in
O(n)
time, the shortest guard diagonal in
O(nα(n))
and the longest guard chord in
O(n)
time of a simple polygon
P
with
n vertices, where
α(n) is the inverse of Ackermann's function.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/S0020-0190(00)00100-9</doi><tpages>6</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0020-0190 |
| ispartof | Information processing letters, 2000-09, Vol.75 (4), p.153-158 |
| issn | 0020-0190 1872-6119 |
| language | eng |
| recordid | cdi_proquest_journals_237280265 |
| source | ScienceDirect Freedom Collection 2022-2024; Backfile Package - Computer Science (Legacy) [YCS]; Backfile Package - Mathematics (Legacy) [YMT] |
| subjects | Algorithms Art galleries & museums Combinatorics Combinatorics. Ordered structures Exact sciences and technology Graph algorithms Graph theory Graphs Mathematics Optimization Sciences and techniques of general use Simple polygon Studies |
| title | Guarding in a simple polygon |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-25T23%3A51%3A53IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Guarding%20in%20a%20simple%20polygon&rft.jtitle=Information%20processing%20letters&rft.au=Lu,%20Bor-Kuan&rft.date=2000-09-30&rft.volume=75&rft.issue=4&rft.spage=153&rft.epage=158&rft.pages=153-158&rft.issn=0020-0190&rft.eissn=1872-6119&rft.coden=IFPLAT&rft_id=info:doi/10.1016/S0020-0190(00)00100-9&rft_dat=%3Cproquest_cross%3E60684741%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c363t-31945b1c0619a5c29919d6910bc634c5221ff7467610c02950b55ff0d051f3d73%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=237280265&rft_id=info:pmid/&rfr_iscdi=true |