Komputer merepresentasikan informasi dari dunia nyata secara digital. Artinya, layar komputer tersusun atas piksel-piksel diskret yang digunakan untuk meniru informasi kontinu dari dunia nyata. Jadi, kita hidup dalam \(\R^3\text{,}\) tetapi layar komputer merepresentasikan informasi dalam \(\Z^2\text{,}\) seperti yang ditunjukkan dalam Gambar 20.10. Kita perlu dapat meniru informasi kontinu secara akurat dari data digital. Salah satu gagasan utamanya adalah memiliki versi digital Teorema Kurva Jordan, yang menyatakan bahwa kurva Jordan (gelung kontinu yang tidak berpotongan dengan dirinya sendiri) pada bidang Euklides memisahkan sisa bidang tersebut menjadi dua komponen terhubung (bagian dalam dan bagian luar kurva). Selain itu, jika satu titik dibuang dari kurva Jordan, sisa bidang tersebut menjadi terhubung. Teorema Kurva Jordan digital penting karena kita hanya perlu menyimpan kurva-kurva Jordan yang menentukan daerah, beserta warna daerah-daerah tersebut, alih-alih harus menyimpan warna setiap piksel dalam sebuah citra.
Gambar20.10.Kiri: bidang digital. Tengah: tetangga-\(4\) dari suatu titik. Kanan: tetangga-\(8\) dari suatu titik.
Langkah awal yang wajar untuk membangun topologi digital adalah mengidentifikasi lingkungan. Gagasan lingkungan adalah mempertimbangkan elemen-elemen yang dekat dengan suatu titik, dan dalam dunia digital terdapat beberapa cara untuk melakukannya. Diberikan titik \((x,y)\) dalam \(\Z^2\text{,}\) tetangga-4 dari \((x,y)\) adalah titik-titik yang bersebelahan secara vertikal atau horizontal dengan \((x,y)\text{,}\) yaitu titik-titik \((x \pm 1, y)\) dan \((x, y \pm 1)\text{.}\) Tetangga-8 dari \((x,y)\) adalah tetangga-4 beserta titik-titik yang bersebelahan secara diagonal dengan \((x,y)\text{,}\) yaitu \((x \pm 1, y)\text{,}\)\((x, y \pm 1)\text{,}\) dan \((x \pm 1, y \pm 1)\text{.}\) Tetangga-tetangga ini ditunjukkan dalam Gambar 20.10, dengan tanda silang yang menunjukkan tetangga dari titik yang disorot.
Dalam kasus kontinu, kita mendefinisikan lintasan antara dua titik sebagai fungsi kontinu dari \([0,1]\) ke ruang tersebut. Namun, kita tidak dapat memiliki kekontinuan dengan cara yang sama dalam dunia digital. Jadi, kita mendefinisikan lintasan dengan bergerak melalui titik-titik tetangga. Artinya, jika \(k\) sama dengan \(4\) atau \(8\text{,}\) lintasan-\(k\) adalah barisan berhingga \(p_0\text{,}\)\(p_1\text{,}\)\(\ldots\text{,}\)\(p_m\) dalam \(\Z^2\) sedemikian sehingga \(p_0\) merupakan tetangga-\(k\) dari \(p_1\text{,}\)\(p_1\) merupakan tetangga-\(k\) dari \(p_2\text{,}\)\(\ldots\text{,}\) dan \(p_{m-1}\) merupakan tetangga-\(k\) dari \(p_m\text{.}\)
Kegiatan20.9.
(a)
Tunjukkan bahwa terdapat lintasan-\(4\) yang menghubungkan sembarang dua titik dalam \(\Z^2\text{.}\) Kemudian jelaskan mengapa terdapat lintasan-\(8\) yang menghubungkan sembarang dua titik dalam \(\Z^2\text{.}\)
(b)
Dalam kasus kontinu, setiap kurva Jordan memisahkan \(\R^2\) menjadi dua daerah terhubung. Untuk memperoleh teorema serupa dalam kasus diskret, kita memerlukan konsep keterhubungan dalam \(\Z^2\text{.}\) Setiap citra tersusun atas sejumlah berhingga piksel, sehingga kita dapat menganggap citra digital berada dalam subruang berhingga dari \(\Z^2\text{.}\) Karena keterhubungan dan keterhubungan lintasan ekuivalen dalam ruang topologi berhingga, kita menggunakan gagasan lintasan-\(k\) untuk mendefinisikan keterhubungan dalam \(\Z^2\text{.}\) Kita mengatakan bahwa subhimpunan \(S\) dari \(\Z^2\)\(terhubung-k\) jika sembarang dua titiknya dapat dihubungkan oleh lintasan-\(k\) dalam \(S\text{.}\)Gambar 20.11 menunjukkan dua himpunan (kurva) pada bidang digital melalui titik-titik yang menghubungkan ruas-ruas garis (contoh diambil dari A Topological Approach to Digital Topology, T. Yung Kong, R. Kopperman, dan P. Meyer, American Mathematical Monthly, 98 (1991), no. 10, 901–917). Misalkan \(S_1\) himpunan yang ditunjukkan di sebelah kiri dalam Gambar 20.11 dan \(S_2\) himpunan di sebelah kanan.
Gambar20.11.Himpunan \(S_1\) (kiri) dan \(S_2\) (kanan) pada bidang digital.
Apakah \(S_1\) terhubung-\(4\text{?}\) Apakah \(S_1\) terhubung-\(8\text{?}\) Periksalah jawaban Anda. Ulangi untuk \(S_2\text{.}\)
(c)
Sekarang kita dapat mendefinisikan kurva Jordan-\(k\) sebagai himpunan berhingga terhubung-\(k\) yang setiap titiknya memiliki tepat dua tetangga-\(k\) di dalam himpunan tersebut. Apakah \(S_1\) merupakan kurva Jordan-\(4\text{?}\) Apakah \(S_1\) merupakan kurva Jordan-\(8\text{?}\) Periksalah jawaban Anda. Ulangi untuk \(S_2\text{.}\)
(d)
Seperti biasa, kita mendefinisikan komponen sebagai himpunan terhubung maksimal. Jelaskan mengapa \(S_1\) merupakan kurva Jordan-\(8\) yang komplemennya terhubung dan mengapa \(S_2\) merupakan kurva Jordan-\(4\) yang komplemennya terdiri atas tiga komponen-\(4\) terhubung. Contoh ini menunjukkan bahwa tidak terdapat Teorema Kurva Jordan dalam topologi digital jika kita menggunakan konsep standar keterhubungan-\(k\) dengan \(k\) sama dengan \(4\) atau \(8\text{.}\) Jadi, baik ketetanggaan-4 maupun ketetanggaan-8 tidak memberikan analog Teorema Kurva Jordan; kita perlu menggunakan kombinasi keduanya. Tepatnya, kurva Jordan-\(4\) dengan sekurang-kurangnya lima titik memisahkan \(\Z^2\) menjadi tepat dua komponen-\(8\text{,}\) dan kurva Jordan-\(8\) dengan sekurang-kurangnya lima titik memisahkan \(\Z^2\) menjadi tepat dua komponen-\(4\text{.}\)
Dalam Kegiatan 20.9, kita membahas pentingnya Teorema Kurva Jordan digital. Dalam kegiatan berikut, kita menjelaskan topologi tempat teorema semacam itu berlaku.
Sekarang kita ingin mendefinisikan kurva Jordan digital. Langkah pertama kita adalah mendefinisikan lintasan digital. Ingat bahwa lintasan dalam ruang topologi adalah daerah hasil suatu fungsi kontinu dari interval \([0,1]\) ke ruang tersebut. Jadi, kita memerlukan konsep interval digital. Jika \(z_1 \lt z_2\) dalam \((\Z, \tau_1)\text{,}\) interval digital \([z_1,z_2]\) adalah himpunan
Bilangan bulat \(z_1\) dan \(z_2\) disebut titik ujung interval digital \([z_1,z_2]\text{.}\)
Definisi20.12.
Misalkan \(X\) ruang topologi.
Lintasan digital dalam \(X\) adalah daerah hasil suatu fungsi kontinu dari interval digital ke \(X\text{.}\)
Busur digital dalam \(X\) adalah daerah hasil suatu homeomorfisme dari interval digital ke \(X\text{.}\)
Definisi20.13.
Kurva Jordan digital adalah himpunan terhubung berhingga \(J\) dengan \(|J| \geq 4\) sedemikian sehingga \(J \setminus \{j\}\) merupakan busur digital untuk setiap \(j \in J\text{.}\)
Kegiatan20.10.
Perhatikan \(\Z\) dengan topologi \(\tau_1\) yang memiliki basis \(\{B(n)\}\text{,}\) dengan
Topologi ini disebut topologi garis digital atau topologi Khalimsky pada \(\Z\text{.}\) Perhatikan bahwa semua himpunan berbentuk \(\{n\}\) buka jika \(n\) ganjil.
(a)
Tunjukkan bahwa setiap himpunan berbentuk \(\{n\}\text{,}\) dengan \(n\) genap, tertutup dalam topologi garis digital.
(b)
Untuk mendefinisikan topologi Khalimsky pada \(\Z^2\text{,}\) kita menggunakan topologi hasil kali. Jelaskan mengapa koleksi himpunan \(\{B(m,n)\}\text{,}\) dengan
\begin{equation*}
B(m,n) = \begin{cases}\{(m,n)\} \amp m \text{ dan } n \text{ ganjil, } \\ \{(m-i,n-j) \mid -1 \leq i \leq 1, -1 \leq j \leq 1\} \amp m \text{ dan } n \text{ genap, } \\ \{(m,n-1), (m,n), (m,n+1)\} \amp m \text{ ganjil dan } n \text{ genap, } \\ \{(m-1,n), (m,n), (m+1,n)\} \amp m \text{ genap dan } n \text{ ganjil } \end{cases}
\end{equation*}
merupakan basis bagi topologi Khalimsky \(\tau_2\) pada \(\Z^2\text{.}\) (Topologi ini pertama kali diterbitkan oleh E. Khalimsky dalam Applications of connected ordered topological spaces in topology, Conference of math. departments of Povolsia, 1970.)
Tunjukkan bahwa \(S_1\) bukan lintasan digital, tetapi \(S_2\) dan \(S_3\) merupakan lintasan digital.
(d)
Untuk menghasilkan Teorema Kurva Jordan digital, kita menggunakan definisi kurva Jordan digital di atas.
Jadi, setiap kurva Jordan digital merupakan himpunan terhubung. Tunjukkan bahwa setiap lintasan digital berhingga dalam \(\Z^2\) merupakan himpunan terhubung.
Kesimpulan pembahasan ini adalah teorema setelah kegiatan ini (pembuktiannya dapat ditemukan dalam A Topological Approach to Digital Topology, T. Yung Kong, R. Kopperman, dan P. Meyer, American Mathematical Monthly, 98 (1991), no. 10, 901–917).
Dua komponen dalam Teorema 20.14 membagi bidang digital menjadi daerah tak berhingga (bagian luar) dan daerah berhingga (bagian dalam).
Tunjukkan bahwa \(S_2\) merupakan kurva Jordan digital (dan karena itu membagi \(\Z^2\) menjadi dua komponen terhubung).
Teorema20.14.
Jika \(J\) merupakan kurva Jordan digital dalam bidang digital \(\Z^2\text{,}\) maka \(\Z^2 \setminus J\) memiliki tepat dua komponen.
Kurva Jordan digital, seperti yang dijelaskan dalam Kegiatan 20.10, penting agar kita memiliki Teorema Kurva Jordan digital. Christer O. Kiselman menyajikan teorema berikut untuk mengarakterisasi kurva Jordan digital dalam Discrete Geometry for Computer Imagery, Springer-Verlag, 2000, hlm. 46–56.
Teorema20.15.
Subhimpunan \(J\) dari \(\Z^2\) yang dilengkapi topologi Khalimsky merupakan kurva Jordan digital jika dan hanya jika \(J = \{P_1, P_2, \ldots, P_m\}\) untuk suatu bilangan bulat genap \(m \geq 4\) dan, untuk setiap \(j\text{,}\)\(P_{j-1}\) dan \(P_{j+1}\text{,}\) serta tidak ada titik lainnya, bertetangga dengan \(P_j\text{;}\) selain itu, setiap lintasan yang terdiri atas tiga titik berurutan \(P_{i-1}\text{,}\)\(P_i\text{,}\)\(P_{i+1}\) berbelok di \(P_i\) sebesar \(45^{\circ}\) atau \(90^{\circ}\text{,}\) atau tidak berbelok sama sekali jika \(P_i\) titik murni, dan bergerak lurus jika \(P_i\) titik campuran.
Kita menyelidiki teorema ini dalam kegiatan berikut.
Kegiatan20.11.
(a)
Pertama-tama, kita perlu mendefinisikan istilah-istilah yang sesuai. Misalkan \(X\) ruang topologi. Dua titik \(x\) dan \(y\) dalam \(X\) disebut bertetangga jika \(x \neq y\) dan himpunan \(\{x, y\}\) terhubung. Kemudian misalkan \(N(x)\) merupakan irisan semua lingkungan dari \(x\text{.}\) Tunjukkan bahwa elemen-elemen berbeda \(x\) dan \(y\) dalam ruang topologi \(X\) bertetangga jika dan hanya jika \(x \in N(y)\) atau \(y \in N(x)\text{.}\)
(b)
Titik \((x_1,x_2)\) dalam \(\Z^2\) disebut murni jika \(x_1\) dan \(x_2\) memiliki paritas yang sama. Jika tidak, titik tersebut disebut campuran. Carilah \(N(P)\) jika \(P\) titik murni atau titik campuran.
(c)
Dalam Kegiatan 20.10, kita menunjukkan bahwa himpunan \(S_1 = \{(1,-1), (1,1), (-1,1), (-1,-1)\}\) bukan lintasan digital dan karena itu bukan kurva Jordan digital. Bagian mana dari Teorema 20.15 yang dilanggar oleh \(S_1\text{?}\)
(d)
Dalam Kegiatan 20.10, kita menunjukkan bahwa himpunan \(S_2 = \{(0,0), (1,-1), (2,0), (1,1)\}\) merupakan kurva Jordan digital. Tunjukkan bahwa dalam \(S_2\text{,}\) sifat dari Teorema 20.15 bahwa \(P_{j-1}\) dan \(P_{j+1}\text{,}\) serta tidak ada titik lainnya, bertetangga dengan \(P_j\) dipenuhi untuk setiap \(j\text{.}\)
