Computing the visibility polygon using few variables

Luis Barba; Matias Korman; Stefan Langerman; Rodrigo I. Silveira

doi:10.1007/978-3-642-25591-5_9

Computing the visibility polygon using few variables

Luis Barba, Matias Korman, Stefan Langerman, Rodrigo I. Silveira

研究成果: Conference contribution

7 被引用数 (Scopus)

抄録

We present several algorithms for computing the visibility polygon of a simple polygon from a viewpoint inside the polygon, when the polygon resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in time, where denotes the number of reflex vertices of that are part of the output. The next two algorithms use O(logr) variables, and output the visibility polygon in O(nlogr) randomized expected time or O(nlog ² r) deterministic time, where r is the number of reflex vertices of .

本文言語	English
ホスト出版物のタイトル	Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
ページ	70-79
ページ数	10
DOI	https://doi.org/10.1007/978-3-642-25591-5_9
出版ステータス	Published - 2011
外部発表	はい
イベント	22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan 継続期間: 2011 12月 5 → 2011 12月 8

出版物シリーズ

名前	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
巻	7074 LNCS
ISSN（印刷版）	0302-9743
ISSN（電子版）	1611-3349

Other

Other	22nd International Symposium on Algorithms and Computation, ISAAC 2011
国/地域	Japan
City	Yokohama
Period	11/12/5 → 11/12/8

ASJC Scopus subject areas

理論的コンピュータサイエンス
コンピュータサイエンス（全般）

文献へのアクセス

10.1007/978-3-642-25591-5_9

他のファイルとリンク

引用スタイル

Barba, L., Korman, M., Langerman, S., & Silveira, R. I. (2011). Computing the visibility polygon using few variables. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings (pp. 70-79). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7074 LNCS). https://doi.org/10.1007/978-3-642-25591-5_9

Computing the visibility polygon using few variables. / Barba, Luis; Korman, Matias; Langerman, Stefan その他.

Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. 2011. p. 70-79 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7074 LNCS).

研究成果: Conference contribution

Barba, L, Korman, M, Langerman, S & Silveira, RI 2011, Computing the visibility polygon using few variables. in Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7074 LNCS, pp. 70-79, 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, Japan, 11/12/5. https://doi.org/10.1007/978-3-642-25591-5_9

Barba L, Korman M, Langerman S, Silveira RI. Computing the visibility polygon using few variables. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. 2011. p. 70-79. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-25591-5_9

@inproceedings{13f9db86eab64c21a02df6cb6576e509,

title = "Computing the visibility polygon using few variables",

abstract = "We present several algorithms for computing the visibility polygon of a simple polygon from a viewpoint inside the polygon, when the polygon resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in time, where denotes the number of reflex vertices of that are part of the output. The next two algorithms use O(logr) variables, and output the visibility polygon in O(nlogr) randomized expected time or O(nlog 2 r) deterministic time, where r is the number of reflex vertices of .",

author = "Luis Barba and Matias Korman and Stefan Langerman and Silveira, {Rodrigo I.}",

year = "2011",

doi = "10.1007/978-3-642-25591-5_9",

language = "English",

isbn = "9783642255908",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "70--79",

booktitle = "Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings",

note = "22nd International Symposium on Algorithms and Computation, ISAAC 2011 ; Conference date: 05-12-2011 Through 08-12-2011",

}

TY - GEN

T1 - Computing the visibility polygon using few variables

AU - Barba, Luis

AU - Korman, Matias

AU - Langerman, Stefan

AU - Silveira, Rodrigo I.

PY - 2011

Y1 - 2011

N2 - We present several algorithms for computing the visibility polygon of a simple polygon from a viewpoint inside the polygon, when the polygon resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in time, where denotes the number of reflex vertices of that are part of the output. The next two algorithms use O(logr) variables, and output the visibility polygon in O(nlogr) randomized expected time or O(nlog 2 r) deterministic time, where r is the number of reflex vertices of .

AB - We present several algorithms for computing the visibility polygon of a simple polygon from a viewpoint inside the polygon, when the polygon resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in time, where denotes the number of reflex vertices of that are part of the output. The next two algorithms use O(logr) variables, and output the visibility polygon in O(nlogr) randomized expected time or O(nlog 2 r) deterministic time, where r is the number of reflex vertices of .

UR - http://www.scopus.com/inward/record.url?scp=84055193601&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84055193601&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-25591-5_9

DO - 10.1007/978-3-642-25591-5_9

M3 - Conference contribution

AN - SCOPUS:84055193601

SN - 9783642255908

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 70

EP - 79

BT - Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings

T2 - 22nd International Symposium on Algorithms and Computation, ISAAC 2011

Y2 - 5 December 2011 through 8 December 2011

ER -

Computing the visibility polygon using few variables

抄録

出版物シリーズ

Other

ASJC Scopus subject areas

文献へのアクセス

他のファイルとリンク

フィンガープリント

引用スタイル