On the number of views of polyhedral scenes

Boris Aronov; Hervé Brönnimann; Dan Halperin; Robert Schiffenbauer

doi:10.1007/3-540-47738-1_6

On the number of views of polyhedral scenes

Boris Aronov, Hervé Brönnimann, Dan Halperin, Robert Schiffenbauer

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

It is known that a scene consisting of A- convex polyhedra of total complexity n has at most 0(n⁴ k²) distinct orthographic views, and that the number of such views is Ω((nk² + n²)²) in the worst case. The corresponding bounds for perspective views are 0(n⁶ k³) and Ω((nk²+n²)³), respectively. In this paper, we close these gaps by improving the lower bounds. We construct an example of a scene with Ө(n⁴ k²) orthographic views, and another with Ө(n⁶ k³) perspective views. Our construction can also be used to improve the known lower bounds for the number of silhouette views and for the number of distinct views from a viewpoint moving along a straight line.

Original language	English (US)
Title of host publication	Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers
Editors	Jin Akiyama, Mikio Kano, Masatsugu Urabe
Publisher	Springer Verlag
Pages	81-90
Number of pages	10
ISBN (Print)	9783540477389
DOIs	https://doi.org/10.1007/3-540-47738-1_6
State	Published - 2001
Event	Japanese Conference on Discrete and Computational Geometry, JCDCG 2000 - Tokyo, Japan Duration: Nov 22 2000 → Nov 25 2000

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2098
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	Japanese Conference on Discrete and Computational Geometry, JCDCG 2000
Country/Territory	Japan
City	Tokyo
Period	11/22/00 → 11/25/00

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-47738-1_6

Cite this

Aronov, B., Brönnimann, H., Halperin, D., & Schiffenbauer, R. (2001). On the number of views of polyhedral scenes. In J. Akiyama, M. Kano, & M. Urabe (Eds.), Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers (pp. 81-90). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2098). Springer Verlag. https://doi.org/10.1007/3-540-47738-1_6

On the number of views of polyhedral scenes. / Aronov, Boris; Brönnimann, Hervé; Halperin, Dan et al.
Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers. ed. / Jin Akiyama; Mikio Kano; Masatsugu Urabe. Springer Verlag, 2001. p. 81-90 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2098).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aronov, B, Brönnimann, H, Halperin, D & Schiffenbauer, R 2001, On the number of views of polyhedral scenes. in J Akiyama, M Kano & M Urabe (eds), Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2098, Springer Verlag, pp. 81-90, Japanese Conference on Discrete and Computational Geometry, JCDCG 2000, Tokyo, Japan, 11/22/00. https://doi.org/10.1007/3-540-47738-1_6

Aronov B, Brönnimann H, Halperin D, Schiffenbauer R. On the number of views of polyhedral scenes. In Akiyama J, Kano M, Urabe M, editors, Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers. Springer Verlag. 2001. p. 81-90. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-47738-1_6

Aronov, Boris ; Brönnimann, Hervé ; Halperin, Dan et al. / On the number of views of polyhedral scenes. Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers. editor / Jin Akiyama ; Mikio Kano ; Masatsugu Urabe. Springer Verlag, 2001. pp. 81-90 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e9df914e351d43e0b1e6e6abd684e670,

title = "On the number of views of polyhedral scenes",

abstract = "It is known that a scene consisting of A- convex polyhedra of total complexity n has at most 0(n4 k2) distinct orthographic views, and that the number of such views is Ω((nk2 + n2)2) in the worst case. The corresponding bounds for perspective views are 0(n6 k3) and Ω((nk2+n2)3), respectively. In this paper, we close these gaps by improving the lower bounds. We construct an example of a scene with Ө(n4 k2) orthographic views, and another with Ө(n6 k3) perspective views. Our construction can also be used to improve the known lower bounds for the number of silhouette views and for the number of distinct views from a viewpoint moving along a straight line.",

author = "Boris Aronov and Herv{\'e} Br{\"o}nnimann and Dan Halperin and Robert Schiffenbauer",

year = "2001",

doi = "10.1007/3-540-47738-1_6",

language = "English (US)",

isbn = "9783540477389",

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

publisher = "Springer Verlag",

pages = "81--90",

editor = "Jin Akiyama and Mikio Kano and Masatsugu Urabe",

booktitle = "Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers",

note = "Japanese Conference on Discrete and Computational Geometry, JCDCG 2000 ; Conference date: 22-11-2000 Through 25-11-2000",

}

TY - GEN

T1 - On the number of views of polyhedral scenes

AU - Aronov, Boris

AU - Brönnimann, Hervé

AU - Halperin, Dan

AU - Schiffenbauer, Robert

PY - 2001

Y1 - 2001

N2 - It is known that a scene consisting of A- convex polyhedra of total complexity n has at most 0(n4 k2) distinct orthographic views, and that the number of such views is Ω((nk2 + n2)2) in the worst case. The corresponding bounds for perspective views are 0(n6 k3) and Ω((nk2+n2)3), respectively. In this paper, we close these gaps by improving the lower bounds. We construct an example of a scene with Ө(n4 k2) orthographic views, and another with Ө(n6 k3) perspective views. Our construction can also be used to improve the known lower bounds for the number of silhouette views and for the number of distinct views from a viewpoint moving along a straight line.

AB - It is known that a scene consisting of A- convex polyhedra of total complexity n has at most 0(n4 k2) distinct orthographic views, and that the number of such views is Ω((nk2 + n2)2) in the worst case. The corresponding bounds for perspective views are 0(n6 k3) and Ω((nk2+n2)3), respectively. In this paper, we close these gaps by improving the lower bounds. We construct an example of a scene with Ө(n4 k2) orthographic views, and another with Ө(n6 k3) perspective views. Our construction can also be used to improve the known lower bounds for the number of silhouette views and for the number of distinct views from a viewpoint moving along a straight line.

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

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

U2 - 10.1007/3-540-47738-1_6

DO - 10.1007/3-540-47738-1_6

M3 - Conference contribution

AN - SCOPUS:84974717485

SN - 9783540477389

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

SP - 81

EP - 90

BT - Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers

A2 - Akiyama, Jin

A2 - Kano, Mikio

A2 - Urabe, Masatsugu

PB - Springer Verlag

T2 - Japanese Conference on Discrete and Computational Geometry, JCDCG 2000

Y2 - 22 November 2000 through 25 November 2000

ER -

On the number of views of polyhedral scenes

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this