Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Khalimsky-Like Topology on the Triangular Grid

  • Conference paper
Discrete Geometry and Mathematical Morphology (DGMM 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14605))

  • 234 Accesses

Abstract

It is well known that there are topological paradoxes in digital geometry and in digital image processing. The most studied such paradoxes are on the square grid, causing the fact that the digital version of the Jordan curve theorem needs some special care. In a nutshell, the paradox can be interpreted by lines, e.g., two different color diagonals of a chessboard that go through each other without sharing a pixel. The triangular grid also has a similar paradox, here diamond chains of different directions may cross each other without having an intersection trixel (triangle pixel). In this paper, a new topology is offered on the triangular grid, which gives a solution to the topological problems in the triangular grid analogous to the Khalimsky’s solution on the square grid.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 119.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 159.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Abdalla, M., Nagy, B.: Dilation and erosion on the triangular tessellation: an independent approach. IEEE Access 6, 23108–23119 (2018)

    Article  Google Scholar 

  2. Abdalla, M., Nagy, B.: Mathematical morphology on the triangular grid: the strict approach. SIAM J. Imaging Sci. 13, 1367–1385 (2020)

    Article  MathSciNet  Google Scholar 

  3. Abuhmaidan, K., Nagy, B.: Bijective, non-bijective and semi-bijective translations on the triangular plane. Mathematics 8/1, paper 29 (2020)

    Google Scholar 

  4. Brimkov, W.E., Barneva, R.P.: Analytical honeycomb geometry for raster and volume graphics. Comput. J. 48(2), 180–199 (2005)

    Article  Google Scholar 

  5. Čomić, L.: Convex and concave vertices on a simple closed curve in the triangular grid. In: Couprie, M., Cousty, J., Kenmochi, Y., Mustafa, N. (eds.) DGCI 2019. LNCS, vol. 11414, pp. 397–408. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-14085-4_31

    Chapter  Google Scholar 

  6. Čomić, L.: Gaps and well-composed objects in the triangular grid. In: Marfil, R., Calderón, M., Díaz del Río, F., Real, P., Bandera, A. (eds.) CTIC 2019. LNCS, vol. 11382, pp. 54–67. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-10828-1_5

    Chapter  Google Scholar 

  7. Conway, J.H., Burgiel, H., Goodman-Strauss, C.: The Symmetries of Things. AK Peters (2008)

    Google Scholar 

  8. Deutsch, E.S.: Thinning algorithms on rectangular, hexagonal and triangular arrays. Commun. ACM 15(3), 827–837 (1972)

    Article  Google Scholar 

  9. Grünbaum, B., Shephard, G.C.: Tilings by regular polygons. Math. Mag. 50(5), 227–247 (1977)

    Article  MathSciNet  Google Scholar 

  10. Hartman, N.P., Tanimoto, S.L.: A hexagonal pyramid data structure for image processing. IEEE Trans. Syst. Man Cybern. 14(2), 247–256 (1984)

    Article  Google Scholar 

  11. Her, I.: A symmetrical coordinate frame on the hexagonal grid for computer graphics and vision. ASME J. Mech. Design 115(3), 447–449 (1993)

    Article  Google Scholar 

  12. Kardos, P., Palágyi, K.: On topology preservation of mixed operators in triangular, square, and hexagonal grids. Discret. Appl. Math. 216, 441–448 (2017)

    Article  MathSciNet  Google Scholar 

  13. Khalimsky, E.D., Kopperman, R., Meyer, P.R.: Computer graphics and connected topologies on finite ordered sets. Topol. Appl. 36, 1–17 (1990)

    Article  MathSciNet  Google Scholar 

  14. Khalimsky, E.D., Kopperman, R., Meyer, P.R.: Boundaries in digital planes. J. Appl. Math. Stoch. Anal. 3, 27–55 (1990)

    Article  MathSciNet  Google Scholar 

  15. Kiselman, C.O.: Digital Jordan curve theorems. In: Borgefors, G., Nyström, I., di Baja, G.S. (eds.) DGCI 2000. LNCS, vol. 1953, pp. 46–56. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44438-6_5

    Chapter  Google Scholar 

  16. Kiselman, C.O.: Elements of Digital Geometry, Mathematical Morphology, and Discrete Optimization. World Scientific, Singapore (2022)

    Book  Google Scholar 

  17. Klette, R., Rosenfeld, A.: Digital Geometry - Geometric Methods for Digital Picture Analysis. Morgan Kaufmann, Elsevier Science B.V (2004)

    Google Scholar 

  18. Kong, T.Y., Kopperman, R., Meyer, P.R.: A topological approach to digital topology. Am. Math. Mon. 98, 902–917 (1991)

    Article  MathSciNet  Google Scholar 

  19. Kong, T.Y., Rosenfeld, A. (eds.): Topological Algorithms for Digital Image Processing. Elsevier, Amsterdam (1996)

    Google Scholar 

  20. Kovács, G., Nagy, B., Stomfai, G., Turgay, N.D., Vizvári, B.: On chamfer distances on the square and body-centered cubic grids: an operational research approach. Math. Probl. Eng. 2021, 1–9 (2021). Article ID 5582034

    Article  Google Scholar 

  21. Kovács, G., Nagy, B., Vizvári, B.: On weighted distances on the Khalimsky grid. In: Normand, N., Guédon, J., Autrusseau, F. (eds.) DGCI 2016. LNCS, vol. 9647, pp. 372–384. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-32360-2_29

    Chapter  Google Scholar 

  22. Kovács, G., Nagy, B., Vizvári, B.: Weighted distances and digital disks on the Khalimsky grid - disks with holes and islands. J. Math. Imag. Vis. 59, 2–22 (2017)

    Article  MathSciNet  Google Scholar 

  23. Kovács, G., Nagy, B., Vizvári, B.: Weighted distances on the trihexagonal grid. In: Kropatsch, W.G., Artner, N.M., Janusch, I. (eds.) DGCI 2017. LNCS, vol. 10502, pp. 82–93. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66272-5_8

    Chapter  Google Scholar 

  24. Kovács, G., Nagy, B., Vizvári, B.: Weighted distances on the truncated hexagonal grid. Pattern Recognit. Lett. 152, 26–33 (2021)

    Article  Google Scholar 

  25. Kovalevsky, V.: Algorithms in digital geometry based on cellular topology. In: Klette, R., Žunić, J. (eds.) IWCIA 2004. LNCS, vol. 3322, pp. 366–393. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30503-3_27

    Chapter  Google Scholar 

  26. Kovalevsky, V.A.: Geometry of Locally Finite Spaces (Computer Agreeable Topology and Algorithms for Computer Imagery). Editing House Dr. Bärbel Kovalevski, Berlin (2008)

    Google Scholar 

  27. Nagy, B.: Finding shortest path with neighborhood sequences in triangular grids. In: ISPA 2001: 2nd IEEE R8-EURASIP International Symposium, Pula, Croatia, pp. 55–60 (2001)

    Google Scholar 

  28. Nagy, B.: A family of triangular grids in digital geometry. In: ISPA 2003: 3rd International Symposium on Image and Signal Processing and Analysis, Rome, Italy, pp. 101–106 (2003)

    Google Scholar 

  29. Nagy, B.: A symmetric coordinate frame for hexagonal networks. In: Theoretical Computer Science - Information Society (ACM Conference), Ljubljana, Slovenia, pp. 193–196 (2004)

    Google Scholar 

  30. Nagy, B.: Optimal neighborhood sequences on the hexagonal grid. In: ISPA 2007: 5th International Symposium, Istanbul, Turkey, pp. 310–315. IEEE (2007)

    Google Scholar 

  31. Nagy, B.: Cellular topology on the triangular grid. In: Barneva, R.P., Brimkov, V.E., Aggarwal, J.K. (eds.) IWCIA 2012. LNCS, vol. 7655, pp. 143–153. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34732-0_11

    Chapter  Google Scholar 

  32. Nagy, B.: Cellular topology and topological coordinate systems on the hexagonal and on the triangular grids. Ann. Math. Artif. Intell. 75(1–2), 117–134 (2015)

    Article  MathSciNet  Google Scholar 

  33. Nagy, B.: Diagrams based on the hexagonal and triangular grids. Acta Polytech. Hung. 19(4), 27–42 (2022)

    Article  Google Scholar 

  34. Nagy, B.: Non-traditional 2D grids in combinatorial imaging - advances and challenges. In: Barneva, R.P., Brimkov, V.E., Nordo, G. (eds.) IWCIA 2022. LNCS, vol. 13348, pp. 3–27. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-23612-9_1

    Chapter  Google Scholar 

  35. Nagy, B., Moisi, E.V.: Memetic algorithms for reconstruction of binary images on triangular grids with 3 and 6 projections. Appl. Soft Comput. 52, 549–565 (2017)

    Article  Google Scholar 

  36. Nagy, B., Strand, R.: A connection between \(\mathbb{Z} ^{n}\) and generalized triangular grids. In: Bebis, G., et al. (eds.) ISVC 2008. LNCS, vol. 5359, pp. 1157–1166. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89646-3_115

    Chapter  Google Scholar 

  37. Radványi, A.G.: On the rectangular grid representation of general CNN networks. Int. J. Circuit Theory Appl. 30(2–3), 181–193 (2002)

    Article  Google Scholar 

  38. Saadat, M., Nagy, B.: Digital geometry on the dual of some semi-regular tessellations. In: Lindblad, J., Malmberg, F., Sladoje, N. (eds.) DGMM 2021. LNCS, vol. 12708, pp. 283–295. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-76657-3_20

    Chapter  Google Scholar 

  39. Slapal, J.: A digital analogue of the Jordan curve theorem. Discret. Appl. Math. 139(1–3), 231–251 (2004)

    Article  MathSciNet  Google Scholar 

  40. Slapal, J.: A Jordan curve theorem with respect to a pretopology on \(Z^2\). Int. J. Comput. Math. 90(8), 1618–1628 (2013)

    Article  Google Scholar 

  41. Slapal, J.: Convenient adjacencies for structuring the digital plane. Ann. Math. Artif. Intell. 75(1–2), 69–88 (2015)

    Article  MathSciNet  Google Scholar 

  42. Slapal, J.: Alexandroff pretopologies for structuring the digital plane. Discret. Appl. Math. 216, 323–334 (2017)

    Article  MathSciNet  Google Scholar 

  43. Stojmenovic, I.: Honeycomb networks: topological properties and communication algorithms. IEEE Trans. Parallel Distrib. Syst. 8, 1036–1042 (1997)

    Article  Google Scholar 

  44. Wiederhold, P., Morales, S.: Thinning on quadratic, triangular, and hexagonal cell complexes. In: Brimkov, V.E., Barneva, R.P., Hauptman, H.A. (eds.) IWCIA 2008. LNCS, vol. 4958, pp. 13–25. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78275-9_2

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University, Famagusta, North Cyprus, Mersin-10, Turkey

    Benedek Nagy

  2. Department of Computer Science, Institute of Mathematics and Informatics, Eszterházy Károly Catholic University, Eger, Hungary

    Benedek Nagy

Authors
  1. Benedek Nagy
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Benedek Nagy .

Editor information

Editors and Affiliations

  1. University of Siena, Siena, Italy

    Sara Brunetti

  2. University of Firenze, Firenze, Italy

    Andrea Frosini

  3. University of Siena, Siena, Italy

    Simone Rinaldi

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Cite this paper

Nagy, B. (2024). A Khalimsky-Like Topology on the Triangular Grid. In: Brunetti, S., Frosini, A., Rinaldi, S. (eds) Discrete Geometry and Mathematical Morphology. DGMM 2024. Lecture Notes in Computer Science, vol 14605. Springer, Cham. https://doi.org/10.1007/978-3-031-57793-2_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-57793-2_12

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-57792-5

  • Online ISBN: 978-3-031-57793-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships