Approximation Algorithms for Finding Best Viewpoints

Houle, Michael E. and Webber, Richard (1998) Approximation Algorithms for Finding Best Viewpoints. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 210-223 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_16).

Full text not available from this repository.

Abstract

We address the problem of finding viewpoints that preserve the relational structure of a three-dimensional graph drawing under orthographic parallel projection. Previously, algorithms for finding the best viewpoints under two natural models of viewpoint “goodness” were proposed. Unfortunately, the inherent combinatorial complexity of the problem makes finding exact solutions is impractical. In this paper, we propose two approximation algorithms for the problem, commenting on their design, and presenting results on their performance.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_16
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.999 Others
P Styles > P.060 3D
ID Code:289

Repository Staff Only: item control page

References

P.K. Agarwal. Intersection and decomposition Algorithms for planar arrangements; Cambridge University Press.

P. Bose, F. Gomez, P. Ramos, and G. Toussaint. Drawing nice projections of objects in space. In Proc. 3rs Int. Symp. Graph Drawing (Passau, Germany), LNCS 1027:52-63, Springer-Verlag, 1995.

M.L. Braunstein. Depth perception through motion. Academic press, 1976.

I. Bruß and A. Frick. Fast interactive 3-d graph visualization. Graph Drawing (Proc. GD '95), volume 1027 of LNCS, pages 99-110. Springer-Verlag, 1996.

T. Calamoneri and A. Massini. On three dimensional layout of interconnection networks. In Proc. 5th Int. Symp. Graph drawing (Rome), LNCS 1353:64-75, Springer-Verlag, 1997.

R.F. Cohen, P. Eades, T. Lin, and F. Ruskey. Three-dimensional graph drawing. Algorithmica, 17(2):199-208, 1996.

P. Eades, M. Houle, and R. Webber, Finding the best Viewpoints for three-dimensional graph drawings. In Proc. 5th Int. Symp. Graph drawing (Rome), LNCS 1353:87-98, Springer-Verlag, 1997.

H. Edelsbrunner. Algorithms in combinatorial geometry. Springer-Verlag, 1987.

J.D. Foley, A. van Dam, S.K. Feiner, and J.F. Hughes. Computer Graphics: Principles and Practice. Addison-Wesley, Reading, MA, 1990.

T.M.J. Fruchtermann and E.M. Reingold. Graph drawing by force-directed placement. Software Practice and Experience, 21(11):1129-1164, November 1991.

T. Kamada and S. Kawai. A simple method for computing general position in displaying three-dimensional objects. In Computer Vision, Graphics and Image Processing, 41(1):43-56, 1988.

K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout Adjustment and the Mental Map. J. of Visual Languages and Computing, pages 183-210, June 1995.

R. Motwani. P. Raghavan. Randomized algorithms. Cambridge University Press, 1995.

P.H.J.M. Otten, L.P.P.P. van Ginneken. The annealing algorihtm. Kluwer Academic, 1989.

H. Plantinga, C.R. Dyer. Visibility, Occlusion, and the Aspect Graph. in Int. J. Computer vision, 5(2):137-160, 1990.

C. Ware and G. Franck. Evaluating stereo and motion cues for visualizing information nets in three dimensions. ACM Transactions on Graphics, 15(2):121-140, 1996.

D.R. Wood.(1998). Two-bend three-dimensional orthogonal grid drawing of maximum degree five graphs; in this proceedings.