Good NEWS: partitioning a simple polygon by compass directions

ABSTRACT

Motivated by geographic information retrieval, we study the problem of partitioning a simple polygon into four parts that can be considered as the North, East, West, and South. We list criteria for such partitionings, propose formalizations into geometric problems, and give efficient algorithms. An implementation and tests on country outlines show the results for three different partitionings.

REFERENCES

• 1: A.I. Abdelmoty and B.A. El-Geresy. An intersection-based formalism for representing orientation relations in a geographic database. In 2nd ACM Workshop on Advances in GIS, 1994.
• 2: Karl-Friedrich Böhringer , Bruce Randall Donald , Dan Halperin, The area bisectors of a polygon and force equilibria in programmable vector fields, Proceedings of the thirteenth annual symposium on Computational geometry, p.457-459, June 04-06, 1997, Nice, France [doi>10.1145/262839.263081]
• 3: P. Bose, J. Czyzowicz, E. Kranakis, D. Krizanc, and D. Lessard. Near-optimal partitioning of rectangles and prisms. In Proc. 11th Canad. Conf. Comput. Geom., pages 162--165, 1999.
• 4: P. Bose, J. Czyzowicz, E. Kranakis, D. Krizanc, and A. Maheswari. A note on cutting circles and squares in equal area pieces. In Proc. FUN with Algorithms '98, 1998.
• 5: P.A. Burrough and A.U. Frank, editors. Geographic Objects with Indeterminate Boundaries, volume II of GISDATA. Taylor & Francis, London, 1996.
• 6: Guoray Cai, GeoVSM: An Integrated Retrieval Model for Geographic Information, Proceedings of the Second International Conference on Geographic Information Science, p.65-79, September 25-28, 2002
• 7: Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
• 8: Matthew Díaz , Joseph O'Rourke, Computing the Center of Area of a Polygon, Proceedings of the Workshop on Algorithms and Data Structures, p.171-182, August 17-19, 1989
• 9: M. Díaz and J. O'Rourke. Ham-sandwich sectioning of polygons. In Proc. 2nd Canad. Conf. Comput. Geom., pages 282--286, 1990.
• 10: M. Díaz and J. O'Rourke. Algorithms for computing the center of area of a convex polygon. Visual Comput., 10:432--442, 1994.
• 11: A.U. Frank. Qualitative spatial reasoning: Cardinal directions as an example. IJGIS, 10(3):269--290, 1996.
• 12: Susan Hert. Connected area partitioning. In Abstracts 17th European Workshop Comput. Geom., pages 35--38. Freie Universitat Berlin, 2001.
• 13: Christopher B. Jones , R. Purves , A. Ruas , M. Sanderson , M. Sester , M. van Kreveld , R. Weibel, Spatial information retrieval and geographical ontologies an overview of the SPIRIT project, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564457]
• 14: R. Larson. Geographic information retrieval and spatial browsing. In L.C. Smith and M. Gluck, editors, Geographic Information Systems and Libraries: Patrons, Maps, and Spatial Information, pages 81--124. 1996.
• 15: Maozhen Li , Sheng Zhou , Christopher B. Jones, Multi-agent Systems for Web-Based Map Information Retrieval, Proceedings of the Second International Conference on Geographic Information Science, p.161-180, September 25-28, 2002
• 16: D.M. Mark. Toward a theoretical framework for geographic entitiy types. In A.U. Frank and I. Campari, editors, Spatial Information Theory: A Theoretical Basis for GIS, number 716 in Lect. Notes in Computer Science, pages 270--283. 1993.
• 17: D. J. Peuquet , Ci-Xiang Zhang, An algorithm to determine the directional relationship between arbitrarily-shaped polygons in the plane, Pattern Recognition, v.20 n.1, p.65-74, 1987 [doi>10.1016/0031-3203(87)90018-5]
• 18: Thomas C. Shermer, A linear algorithm for bisecting a polygon, Information Processing Letters, v.41 n.3, p.135-140, March 6, 1992 [doi>10.1016/0020-0190(92)90042-T]
• 19: Leonard Talmy, How Spoken Language and Signed Language Structure Space Differently, Proceedings of the International Conference on Spatial Information Theory: Foundations of Geographic Information Science, p.247-262, September 19-23, 2001
• 20: U. Visser, T. Vogele, and C. Schlieder. Spatio-terminological information retrieval using the BUSTER system. In Proc. of the EnviroInfo, pages 93--100, 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms

Keywords:
equal-area partitioning, simple polygon, spatial information retrieval