Kinetic closest pair
ಚಲನೆಯ ಹತ್ತಿರದ ಜೋಡಿ ದತ್ತಾಂಶ ರಚನೆಯು ಚಲನೆಯ ದತ್ತಾಂಶ ರಚನೆಯಾಗಿದ್ದು, ಇದು ಹತ್ತಿರದ ಜೋಡಿ ಬಿಂದುಗಳನ್ನು ನಿರ್ವಹಿಸುತ್ತದೆ, ಇದು ಮೆಟ್ರಿಕ್ ಜಾಗದಲ್ಲಿ ಸಮಯದೊಂದಿಗೆ ನಿರಂತರವಾಗಿ ಚಲಿಸುವ n ಬಿಂದುಗಳ P ಗುಂಪನ್ನು ನೀಡುತ್ತದೆ. ಸ್ಥಿರ ಪ್ರಕರಣದಲ್ಲಿ ಅನೇಕ ಪರಿಣಾಮಕಾರಿ ಕ್ರಮಾವಳಿಗಳು ತಿಳಿದಿದ್ದರೂ, ಅವು ಚಲನಶೀಲಗೊಳಿಸಲು ಕಷ್ಟವೆಂದು ಸಾಬೀತಾಯಿತು, ಆದ್ದರಿಂದ ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಹೊಸ ಸ್ಥಿರ ಕ್ರಮಾವಳಿಗಳನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಲಾಯಿತು. 2ಡಿ ಕೇಸ್ ಅಪ್ರೋಚ್ 1 ಹತ್ತಿರದ ಜೋಡಿಯ ನಿರ್ವಹಣೆಗೆ ಸರಳವಾದ ಚಲನಶೀಲ ವಿಧಾನವೆಂದರೆ ಡೆಲೌನೆ ತ್ರಿಕೋನಗಳ ರೂಪಾಂತರಗಳನ್ನು ಬಳಸುವುದು. ಒಂದು ಷಟ್ಕೋಣವನ್ನು ಪರಿಗಣಿಸಿ ಮತ್ತು ಅದನ್ನು ಆರು ಸಮಬಾಹು ತ್ರಿಕೋನಗಳಾಗಿ ವಿಭಜಿಸಿ, ನಂತರ ಪ್ರತಿ ಸಮಬಾಹು ತ್ರಿಕೋನದ ಆಧಾರದ ಮೇಲೆ ಡೆಲೌನೆ ತ್ರಿಕೋನವನ್ನು ರಚಿಸಿ, ಏಕೆಂದರೆ ಪ್ರತಿಯೊಂದೂ ಕನ್ವೆಕ್ಸ್ ಆಕಾರದಲ್ಲಿರುತ್ತದೆ. ಈಕ್ವಿಲ್ಯಾಟರಲ್ ಡೆಲಾನೇ ಗ್ರಾಫ್ (ಇಡಿಜಿ) ಎಂದು ಕರೆಯಲ್ಪಡುವ ಈ ಆರು ಡೆಲಾನೇ ತ್ರಿಕೋನಗಳ ಸಂಯೋಜನೆಯು ಹತ್ತಿರದ ನೆರೆಯ ಗ್ರಾಫ್ (ಎನ್ಎನ್ಜಿ) ಗೆ ಸೂಪರ್ಗ್ರಾಫ್ ಆಗಿದೆ; ಇಡಿಜಿಯಲ್ಲಿ ಕನಿಷ್ಠ ಉದ್ದವಿರುವ ಅಂಚಿನ ಅಂತಿಮ ಬಿಂದುಗಳು ಹತ್ತಿರದ ಜೋಡಿಯನ್ನು ನೀಡುತ್ತವೆ. ಕನ್ವೆಕ್ಸ್ ಆಕಾರಗಳ ಆಧಾರದ ಮೇಲೆ ಡೆಲೌನೆ ತ್ರಿಕೋನಗಳನ್ನು ನಿರ್ವಹಿಸುವುದು ಸರಳವಾಗಿದೆ. ಕಾಲಾನಂತರದಲ್ಲಿ ಇ. ಡಿ. ಜಿ. ಯನ್ನು ಗಮನಿಸಿದರೆ, ಇ. ಡಿ. ಜಿ. ಯ ಅಂಚುಗಳ ಮೇಲೆ ಚಲನಶೀಲ ಪಂದ್ಯಾವಳಿ ಮರವನ್ನು ರಚಿಸುವ ಮೂಲಕ, ಒಬ್ಬರು ಸುಲಭವಾಗಿ ಹತ್ತಿರದ ಜೋಡಿಯನ್ನು ನಿರ್ವಹಿಸಬಹುದು. ಈ ಹತ್ತಿರದ ಜೋಡಿ ಕೆ. ಡಿ. ಎಸ್ ದಕ್ಷವಾಗಿದೆ, ಸಾಲ ಮರುಪಾವತಿಗೆ ಸ್ಪಂದಿಸುತ್ತದೆ ಮತ್ತು ಸಾಂದ್ರವಾಗಿರುತ್ತದೆ, ಆದರೆ ಸಾಮಾನ್ಯವಾಗಿ ಸ್ಥಳೀಯವಾಗಿರುವುದಿಲ್ಲ. ಈ ಕೆಳಗಿನ ವಿಧಾನವು ಹತ್ತಿರದ ಜೋಡಿಯ ನಿರ್ವಹಣೆಗಾಗಿ ಸ್ಥಳೀಯ ಕೆ. ಡಿ. ಎಸ್ ಅನ್ನು ಒದಗಿಸುತ್ತದೆ. ವಿಧಾನ 2 ಎರಡನೇ ಚಲನಶೀಲ ವಿಧಾನವು ಈ ಕೆಳಗಿನ ಅವಲೋಕನಗಳನ್ನು ಆಧರಿಸಿದೆ. ಒಂದು ಬಿಂದುವಿನ ಸುತ್ತಲಿನ ಜಾಗವನ್ನು ಕೋನೀಯವಾಗಿ ಆರು "ತುಂಡುಗಳು" ಎಂದು ವಿಂಗಡಿಸಿದರೆ, ಪ್ರತಿಯೊಂದೂ ಅಗಲವಾಗಿದ್ದರೆ, ಪ್ರತಿಯೊಂದು ತುಂಡುಗಳಲ್ಲಿನ ಹತ್ತಿರದ ಬಿಂದುಗಳಿಗೆ ಹತ್ತಿರದ ಬಿಂದುವು ಹತ್ತಿರವಾಗಿರುತ್ತದೆ. ಈ ಲೇಖನದ ಉಳಿದ ಭಾಗವು "ಮುಖ್ಯ" ತುಂಡುಗಳ ಮೇಲೆ ಕೇಂದ್ರೀಕರಿಸುತ್ತದೆ (x-ಅಕ್ಷದಿಂದ ವಿಭಜಿಸಲ್ಪಟ್ಟವು), ಮತ್ತು ಸಮತಟ್ಟಾದ ವಾದಗಳು ಸಮತಲವನ್ನು ತಿರುಗಿಸಿದ ನಂತರ ಇತರ ತುಂಡುಗಳಿಗೆ ಅನ್ವಯಿಸುತ್ತವೆ. ಹೊಂದಾಣಿಕೆಯ ಅಂಕಗಳು ಮತ್ತು ಅವು ಪರಸ್ಪರ ಹತ್ತಿರದ ಅಂಕಗಳಾಗಿದ್ದರೆ "ಹೊಂದಾಣಿಕೆಯಾಗುತ್ತವೆ" ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ. ಸ್ಪಷ್ಟವಾಗಿ, ಹತ್ತಿರದ ಅಂಕಗಳ ಜೋಡಿಯು ಹೊಂದಿಕೆಯಾಗುವ ಜೋಡಿಯಾಗಿದೆ. ಬಿಂದುಗಳನ್ನು ಪರಿಗಣಿಸಿ ಮತ್ತು, ಅದು ಎಡಭಾಗದಲ್ಲಿದೆ ಮತ್ತು ಮೇಲೆ ವಿವರಿಸಿದಂತೆ ಬೆಣೆ ಕೇಂದ್ರದಲ್ಲಿದೆ. ಇದು ಹತ್ತಿರದ ಬಿಂದುವಾಗಿದ್ದರೆ, ಅದು x-ದಿಕ್ಕಿನಲ್ಲಿ (ಈ ಬೆಣೆ) ಹತ್ತಿರದ ಬಿಂದುವಾಗಿರಬೇಕು. ಹೀಗಾಗಿ, x-ದಿಕ್ಕಿನಲ್ಲಿ ಹತ್ತಿರದ ಬಿಂದುಗಳ ಜೋಡಿಗಳ (ಈ ಬೆಣೆ ಒಳಗೆ) ಸೆಟ್ ಹತ್ತಿರದ ಬಿಂದುಗಳ ಜೋಡಿಗಳ ಗುಂಪಿನ ಸೂಪರ್ಸೆಟ್ ಆಗಿದೆ. P ಗುಂಪಿನಲ್ಲಿರುವ ಪ್ರತಿ ಬಿಂದು p = (x, y) ಅನ್ನು ಹೊಸ ಬಿಂದುವಿಗೆ ನಕ್ಷೆ ಮಾಡಿ, ಪರಿವರ್ತಿತ ಬಿಂದುಗಳ ಸೆಟ್ P 'ಅನ್ನು ರೂಪಿಸುತ್ತದೆ. ಒಂದು ಬಿಂದುವಿಗೆ, "ಮುಖ್ಯ" ಬೆಣೆಗಳಲ್ಲಿರುವ ಬಿಂದುಗಳು ಈ ಹೊಸ ನಿರ್ದೇಶಾಂಕ ವ್ಯವಸ್ಥೆಗಿಂತ ದೊಡ್ಡದಾಗಿರುತ್ತವೆ ಅಥವಾ ಚಿಕ್ಕದಾಗಿರುತ್ತವೆ ಮತ್ತು ನಿರ್ದೇಶಾಂಕಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಬಿಂದುಗಳನ್ನು x, u ಮತ್ತು v ನಿರ್ದೇಶಾಂಕಗಳಿಂದ ವಿಂಗಡಿಸಿ ಮತ್ತು ಅವುಗಳನ್ನು ಚಲನಶೀಲ ವಿಂಗಡಿಸಲಾದ ಪಟ್ಟಿಗಳಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ. ಒಳಗೆ ಇರುವ ಬಿಂದುಗಳ ಮೇಲೆ 2ಡಿ ಶ್ರೇಣಿಯ ಟ್ರೀ ಟಿ ಅನ್ನು ನಿರ್ಮಿಸಿ. ಪ್ರಾಥಮಿಕ ಮರದಲ್ಲಿನ ಪ್ರತಿ ನೋಡ್ ಡಬ್ಲ್ಯೂಗೆ, ಟಿ (ಡಬ್ಲ್ಯೂ) ಡಬ್ಲ್ಯೂಗೆ ಸಂಬಂಧಿಸಿದ ದ್ವಿತೀಯ ಮರವಾಗಿರಲಿ. ಈ ಶ್ರೇಣಿಯ ಮರವನ್ನು ಒಂದು ಬಿಂದುವಿಗೆ "ಮುಖ್ಯ" ಬೆಣೆಗಳಲ್ಲಿನ ಬಿಂದುಗಳನ್ನು ಗುರುತಿಸಲು ಬಳಸಲಾಗುತ್ತದೆ. ಪ್ರಾಥಮಿಕ ಮರದಲ್ಲಿನ ಪ್ರತಿ ನೋಡ್ಗೆ, ಮತ್ತು ಟಿ (ಡಬ್ಲ್ಯೂ) ನಲ್ಲಿನ ಪ್ರತಿ ನೋಡ್ ಇಗೆ, ಜೋಡಿಯನ್ನು (ಡಬ್ಲ್ಯೂ, ಇ) = (ಬಿ, ಆರ್) ಲೆಕ್ಕ ಹಾಕಿ, ಅಲ್ಲಿ ಬಿ (ಅಥವಾ ಆರ್) ಅನ್ನು ಇ ನ ಎಡ (ಅಥವಾ ಬಲ) ಸಬ್ಟ್ರೀಯಲ್ಲಿ ಗರಿಷ್ಠ (ಅಥವಾ ಕನಿಷ್ಠ) ಎಕ್ಸ್-ಕೋಆರ್ಡಿನೇಟ್ ಹೊಂದಿರುವ ಬಿಂದು ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಟಿ ಯಲ್ಲಿರುವ ಎಲ್ಲಾ ಜೋಡಿಗಳಿಗೆ (ಡಬ್ಲ್ಯೂ, ಇ) ಸೆಟ್ ಆಗಿರಲಿ. ಇದು ಹತ್ತಿರದ ಬಿಂದುಗಳ ಜೋಡಿಗಳ ಗುಂಪಿನ ಸೂಪರ್ಸೆಟ್ ಆಗಿದೆ (ಮುಖ್ಯ ಬೆಣೆ ಒಳಗೆ). ಜೋಡಿಯಲ್ಲಿನ ಬಿಂದುಗಳ ನಡುವಿನ ಅಂತರದಿಂದ (ಮೂಲ ಸಮನ್ವಯ ವ್ಯವಸ್ಥೆಯಲ್ಲಿ ಅಳೆಯಲಾಗುತ್ತದೆ) ಆದ್ಯತೆಗಳನ್ನು ನಿರ್ಧರಿಸುವ ಮೂಲಕ ಜೋಡಿಗಳ ಮೇಲೆ ಚಲನಶೀಲ ಆದ್ಯತೆಯ ಕ್ಯೂ ಅನ್ನು ನಿರ್ಮಿಸಿ. ಚಲನಾತ್ಮಕ ಆದ್ಯತೆಯ ಸಾಲುಗಳನ್ನು ಕ್ರಮವಾಗಿ ಆನ್ ಮಾಡಲು, ಸಮತಲವನ್ನು ತಿರುಗಿಸಲು ಮೇಲಿನ ಹಂತಗಳನ್ನು ಪುನರಾವರ್ತಿಸಿ. ಪಿ ಯಲ್ಲಿನ ಹತ್ತಿರದ ಜೋಡಿ ಅಂಕಗಳು ಮೇಲಿನ ಮೂರು ಆದ್ಯತೆಯ ಸಾಲುಗಳಿಂದ ಪಡೆದ ಕನಿಷ್ಠ ಕನಿಷ್ಠ ಅಂಕಗಳಿಗೆ ಅನುಗುಣವಾಗಿರುತ್ತವೆ. ಆದ್ಯತೆಯ ಸಾಲುಗಳು ಮತ್ತು ವಿಂಗಡಿಸಲಾದ ಪಟ್ಟಿಗಳಲ್ಲಿ ನಿರ್ವಹಣಾ ಪ್ರಮಾಣಪತ್ರ ವೈಫಲ್ಯಗಳು ಸಂಭವಿಸಬಹುದು. ಅಂಕಗಳ ಕ್ರಮದಲ್ಲಿನ ವಿನಿಮಯವು ಟಿಗೆ ಬದಲಾವಣೆಗಳನ್ನು ಉಂಟುಮಾಡುತ್ತದೆ (ಇದು ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ), ಮತ್ತು ಆದ್ಯತೆಯ ಸಾಲುಗಳಲ್ಲಿ ಅಳವಡಿಕೆ/ಅಳಿಸುವಿಕೆಗೆ ಕಾರಣವಾಗಬಹುದು. ಮೇಲೆ ವ್ಯಾಖ್ಯಾನಿಸಿದಂತೆ ಸೆಟ್ಗಳಲ್ಲಿನ ಬದಲಾವಣೆಗಳ ಸಂಖ್ಯೆಯು ಸ್ಥಿರ ಸಂಖ್ಯೆಯಾಗಿರಬೇಕಾಗಿಲ್ಲ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಆದಾಗ್ಯೂ, p ಮತ್ತು q ಬದಲಾವಣೆಯ ಕ್ರಮದ ಪರಿಣಾಮವಾಗಿ ಹೊಂದಾಣಿಕೆಯಾಗುವುದನ್ನು ಪ್ರಾರಂಭಿಸುವ ಅಥವಾ ನಿಲ್ಲಿಸುವ ಯಾವುದೇ ಜೋಡಿಯು p ಮತ್ತು/ಅಥವಾ q ಅನ್ನು ಹೊಂದಿರಬೇಕು, ಆದ್ದರಿಂದ ಸ್ಥಿರವಾದ ಸಂಖ್ಯೆಯ ಹೊಂದಾಣಿಕೆಯ ಜೋಡಿಗಳನ್ನು ಮಾತ್ರ ಆದ್ಯತೆಯ ಸಾಲುಗಳಲ್ಲಿ ಸೇರಿಸಬೇಕು/ಅಳಿಸಬೇಕು. ಈ ಹೊಂದಾಣಿಕೆಯ ಜೋಡಿಗಳನ್ನು ಮಾತ್ರ ನವೀಕರಿಸುವುದು ಸರಿ, ಏಕೆಂದರೆ ವ್ಯಾಖ್ಯಾನದ ಪ್ರಕಾರ, ಹೊಂದಾಣಿಕೆಯ ಜೋಡಿಗಳು ಮಾತ್ರ ಹತ್ತಿರದ ಜೋಡಿಯಾಗುವ ಅವಕಾಶವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಈ ಕೆ. ಡಿ. ಎಸ್ ವಿಶ್ಲೇಷಣೆ ಹೀಗಿದೆಃ ಪ್ರತಿಕ್ರಿಯಾತ್ಮಕಃ ಘಟನೆಯನ್ನು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಲು ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಸ್ಥಳೀಯಃ ಪ್ರತಿ ಬಿಂದುವು ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಚಲನಶೀಲ ವಿಂಗಡಿಸಲಾದ ಪಟ್ಟಿಗಳು ಮತ್ತು ಚಲನಶೀಲ ಆದ್ಯತೆಯ ಸಾಲುಗಳಲ್ಲಿ ಇರುವುದರಿಂದ, ಆ ರಚನೆಗಳ ಸ್ಥಳದಿಂದ ಸ್ಥಳವು ಅನುಸರಿಸುತ್ತದೆ ಸಾಂದ್ರತೆಃ ಚಲನಶೀಲ ವಿಂಗಡಿಸಲಾದ ಪಟ್ಟಿಗಳು ಮತ್ತು ಚಲನಶೀಲ ಆದ್ಯತೆಯ ಸಾಲುಗಳ ಸಾಂದ್ರತೆಯಿಂದ ಸಾಂದ್ರತೆಯು ಅನುಸರಿಸುತ್ತದೆ ದಕ್ಷತೆಃ ವಿಂಗಡಿಸಲಾದ ಪಟ್ಟಿಗಳಲ್ಲಿನ ಪ್ರತಿ ವಿನಿಮಯವು ಚಲನಶೀಲ ಆದ್ಯತೆಯ ಸಾಲುಗಳಲ್ಲಿ ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಅಳವಡಿಕೆ ಮತ್ತು ಅಳಿಸುವಿಕೆಯನ್ನು ಉಂಟುಮಾಡುತ್ತದೆ. ಬಿಂದುಗಳ ಚಲನೆಯು ಹುಸಿ-ಬೀಜಗಣಿತವಾಗಿದೆ ಎಂದು ಭಾವಿಸಿದರೆ, ಬಹುಪದೀಯ ಸಂಖ್ಯೆಯ ವಿನಿಮಯಗಳಿವೆ, ಮತ್ತು ಆದ್ದರಿಂದ ಬಹುಪದೀಯ ಸಂಖ್ಯೆಯ ಘಟನೆಗಳನ್ನು ಈ ಕೆ. ಡಿ. ಎಸ್. ನಿಂದ ಸಂಸ್ಕರಿಸಲಾಗುತ್ತದೆ, ಇದು ಅದನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಮಾಡುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಚಲನ ದತ್ತಾಂಶ ರಚನೆಗಳು ಜ್ಯಾಮಿತೀಯ ದತ್ತಾಂಶ ರಚನೆಗಳು