Near Pole Polar Diagram of Points and its Duality with Applications

Document Type : Research Article

Authors

Abstract

In this paper we propose a new approach to plane partitioning with similar features to those of Polar Diagram, but we assume that the pole is close to the sites. The result is a new tessellation of the plane in regions called Near Pole Polar Diagram NPPD. Here we define the (NPPD) of points, the dual and the Contracted dual of it, present an optimal algorithms to draw them and discuss the applications and optimality of the algorithms.

Keywords

References

[1]     B. Sadeghi Bigham, A. Mohades, Polar diagram with respect to a near pole, in: 23rd European Workshop on Computational Geometry EWCG07, Austria,206-209, 2007.
[2]     C. I. Grima, A. M´arquez and L. Ortega, A new 2D tessellation for angle problems: The polar diagram. Computational Geometry, 34 (2006) 58-74.
[3]      B. Sadeghi Bigham, A. Mohades, The Dual of Polar diagrams and its extraction, in: International Conference of Computational Methods in Sciences and Engineering (ICCMSE), Greece, (2006) 451-454.
[4]      Zahra Nilforoushan, Ali Mohades, Hyperbolic Voronoi Diagram. ICCSA (5), (2006) 735-742.
[5]     C.I. Grima, A. M´arquez, Computational Geometry on Surfaces, Kluwer Academic Publishers, 2001.
[6]     A. Okabe, B. Boots, K. Sugihara, S.N. Chiu, Spatial Tessellations Concepts and Applications of Voronoi Diagrams, second ed., Wiley, Chichester, 2000.
[7]     O. Aichholzer, F. Aurenhammer, D.Z. Chen, D.T. Lee, Skew Voronoi diagrams, Internat. J. Comput. Geometry Appl. 9 (1999) 235-247.
[8]     C.I. Grima, A. M´arquez, L. Ortega, A locus approach to angle problems in computational geometry, in: 14th European Workshop in Computational Geometry, Barcelona, Spain, 1998.
[9]     S. Fortune,Voronoi diagrams and Delaunay triangulations, in: D.-Z. Du, F.K.Hwang (Eds.), Computing in Euclidean Geometry,World Scientific Publishing, Singapore, 1992, pp. 193-233.
[10]  F. Aurenhammer, Voronoi diagrams a survey of a fundamental geometric data structure, ACM Comput. Surveys 23 (1991) 345-405.
[11]  B. Aronov, On the geodesic Voronoi diagram of point sites in a simple polygon, Algorithmica 4 (1989) 109-140.
[12]  F. Aurenhammer, Power diagrams-properties, algorithms and applications, SIAM J. Comput. 16 (1987) 78-96.
[13]  P.F. Ash, E.D. Bolker, Generalized Dirichlet tessellations, Geom. Dedicata 20 (1986) 209-243.
[14]  H. Imai, M. Iri, K. Murota, Voronoi diagram in the Laguerre geometry and its applications, SIAM J. Comput. 14 (1985) 93-105.
[15]  F. Aurenhammer, H. Edelsbrunner, An optimal algorithm for constructing the weighted Voronoi diagram in the plane, Pattern Recognition 17 (1984) 251-257.
[16]  D.-T. Lee, Two-dimensional Voronoi diagrams in the Lp-metric, J. ACM 27 (1980) 604-618.

Files

Share

How to cite

Statistics