Klee's measure problem
ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿಯಲ್ಲಿ, ಕ್ಲೀಯ ಅಳತೆಯ ಸಮಸ್ಯೆಯು (ಬಹುಆಯಾಮದ) ಆಯತಾಕಾರದ ಶ್ರೇಣಿಗಳ ಒಕ್ಕೂಟದ ಅಳತೆಯನ್ನು ಎಷ್ಟು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಇಲ್ಲಿ, ಡಿ-ಆಯಾಮದ ಆಯತಾಕಾರದ ವ್ಯಾಪ್ತಿಯನ್ನು ನೈಜ ಸಂಖ್ಯೆಗಳ ಡಿ ಮಧ್ಯಂತರಗಳ ಕಾರ್ಟೇಶಿಯನ್ ಉತ್ಪನ್ನವೆಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ, ಇದು ಆರ್ಡಿ ಯ ಉಪವಿಭಾಗವಾಗಿದೆ. ಈ ಸಮಸ್ಯೆಯನ್ನು ವಿಕ್ಟರ್ ಕ್ಲೀ ಅವರ ಹೆಸರನ್ನು ಇಡಲಾಗಿದೆ, ಅವರು ಮಧ್ಯಂತರಗಳ ಒಕ್ಕೂಟದ ಉದ್ದವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೀಡಿದರು (ಕೇಸ್ ಡಿ = 1) ಇದನ್ನು ನಂತರ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದ ಅರ್ಥದಲ್ಲಿ ಅತ್ಯುತ್ತಮವಾಗಿ ಪರಿಣಾಮಕಾರಿಯಾಗಿದೆ ಎಂದು ತೋರಿಸಲಾಗಿದೆ. 2-ಆಯಾಮದ ಆಯತಾಕಾರದ ಶ್ರೇಣಿಗಳ ಒಕ್ಕೂಟದ ಪ್ರದೇಶವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯು ಈಗ ತಿಳಿದಿದೆ, ಆದರೆ ಪ್ರಕರಣ d ≤3 ಒಂದು ಮುಕ್ತ ಸಮಸ್ಯೆಯಾಗಿ ಉಳಿದಿದೆ. ಇತಿಹಾಸ ಮತ್ತು ಕ್ರಮಾವಳಿಗಳು 1977 ರಲ್ಲಿ, ವಿಕ್ಟರ್ ಕ್ಲೀ ಈ ಕೆಳಗಿನ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಗಣಿಸಿದರುಃ ನೈಜ ರೇಖೆಯಲ್ಲಿ n ಮಧ್ಯಂತರಗಳ ಸಂಗ್ರಹವನ್ನು ನೀಡಿದರೆ, ಅವುಗಳ ಒಕ್ಕೂಟದ ಉದ್ದವನ್ನು ಲೆಕ್ಕ ಹಾಕಿ. ನಂತರ ಅವರು ಈ ಸಮಸ್ಯೆಯನ್ನು ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯೊಂದಿಗೆ (ಅಥವಾ "ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯ") ಪರಿಹರಿಸಲು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಿದರು-ಈ ಹೇಳಿಕೆಯ ಅರ್ಥಕ್ಕಾಗಿ ಬಿಗ್ ಓ ಸಂಕೇತವನ್ನು ನೋಡಿ. ಮಧ್ಯಂತರಗಳನ್ನು ವಿಂಗಡಿಸುವುದನ್ನು ಆಧರಿಸಿದ ಈ ಕ್ರಮಾವಳಿಯನ್ನು ನಂತರ ಮೈಕೆಲ್ ಫ್ರೆಡ್ಮನ್ ಮತ್ತು ಬ್ರೂಸ್ ವೈಡ್ (1978) ಅತ್ಯುತ್ತಮವೆಂದು ತೋರಿಸಿದರು. ನಂತರ 1977 ರಲ್ಲಿ, ಜಾನ್ ಬೆಂಟ್ಲೆ ಈ ಸಮಸ್ಯೆಯ ಎರಡು ಆಯಾಮದ ಸಾದೃಶ್ಯವನ್ನು ಪರಿಗಣಿಸಿದರುಃ n ಆಯತಗಳ ಸಂಗ್ರಹವನ್ನು ನೀಡಿದರೆ, ಅವುಗಳ ಒಕ್ಕೂಟದ ಪ್ರದೇಶವನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ. ಅವರು ಸಂಕೀರ್ಣತೆಯ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸಹ ಪಡೆದರು, ಇದನ್ನು ಈಗ ಬೆಂಟ್ಲಿಯ ಅಲ್ಗಾರಿದಮ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಇದು ಸಮಸ್ಯೆಯನ್ನು n 1-ಆಯಾಮದ ಸಮಸ್ಯೆಗಳಿಗೆ ಕಡಿಮೆ ಮಾಡುವುದರ ಮೇಲೆ ಆಧಾರಿತವಾಗಿದೆಃ ಇದನ್ನು ಪ್ರದೇಶದಾದ್ಯಂತ ಲಂಬವಾದ ರೇಖೆಯನ್ನು ಉಜ್ಜುವ ಮೂಲಕ ಮಾಡಲಾಗುತ್ತದೆ. ಈ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು, ಒಕ್ಕೂಟದ ಪ್ರದೇಶವನ್ನು ಸ್ಪಷ್ಟವಾಗಿ ಒಕ್ಕೂಟವನ್ನು ನಿರ್ಮಿಸದೆ ಲೆಕ್ಕ ಹಾಕಬಹುದು. ಬೆಂಟ್ಲಿಯ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಈಗ ಸೂಕ್ತವೆಂದು ಕರೆಯಲಾಗುತ್ತದೆ (2-ಆಯಾಮದ ಸಂದರ್ಭದಲ್ಲಿ), ಮತ್ತು ಇದನ್ನು ಇತರ ಕ್ಷೇತ್ರಗಳ ಜೊತೆಗೆ ಕಂಪ್ಯೂಟರ್ ಗ್ರಾಫಿಕ್ಸ್ನಲ್ಲಿ ಬಳಸಲಾಗುತ್ತದೆ. ಈ ಎರಡು ಸಮಸ್ಯೆಗಳು ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ಪ್ರಶ್ನೆಯ 1-ಮತ್ತು 2-ಆಯಾಮದ ಪ್ರಕರಣಗಳಾಗಿವೆಃ nd-ಆಯಾಮದ ಆಯತಾಕಾರದ ಶ್ರೇಣಿಗಳ ಸಂಗ್ರಹವನ್ನು ನೀಡಿದರೆ, ಅವುಗಳ ಒಕ್ಕೂಟದ ಅಳತೆಯನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ. ಈ ಸಾಮಾನ್ಯ ಸಮಸ್ಯೆಯು ಕ್ಲೀಯ ಅಳತೆಯ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಡಿ-ಡೈಮೆನ್ಷನಲ್ ಕೇಸ್ಗೆ ಸಾಮಾನ್ಯೀಕರಿಸಿದಾಗ, ಬೆಂಟ್ಲಿಯ ಅಲ್ಗಾರಿದಮ್ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವನ್ನು ಹೊಂದಿದೆ. ಇದು ಸೂಕ್ತವಲ್ಲ ಎಂದು ಸಾಬೀತಾಗುತ್ತದೆ, ಏಕೆಂದರೆ ಇದು ಡಿ-ಆಯಾಮದ ಸಮಸ್ಯೆಯನ್ನು ಎನ್ (ಡಿ-1)-ಆಯಾಮದ ಸಮಸ್ಯೆಗಳಾಗಿ ಮಾತ್ರ ವಿಭಜನೆ ಮಾಡುತ್ತದೆ ಮತ್ತು ಆ ಉಪ-ಸಮಸ್ಯೆಗಳನ್ನು ಮತ್ತಷ್ಟು ವಿಭಜನೆ ಮಾಡುವುದಿಲ್ಲ. 1981ರಲ್ಲಿ, ಜಾನ್ ವ್ಯಾನ್ ಲೀವೆನ್ ಮತ್ತು ಡೆರೆಕ್ ವುಡ್ ಅವರು ಡೈನಾಮಿಕ್ ಕ್ವಾಡ್ಟ್ರೀಗಳನ್ನು ಬಳಸುವ ಮೂಲಕ ಈ ಅಲ್ಗಾರಿದಮ್ನ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವನ್ನು ಡಿ ≤3ಗೆ ಸುಧಾರಿಸಿದರು. 1988ರಲ್ಲಿ, ಮಾರ್ಕ್ ಓವರ್ಮಾರ್ಸ್ ಮತ್ತು ಚೀ ಯಾಪ್ರವರು ಡಿ ≤3ಗಾಗಿ ಒಂದು ಕ್ರಮಾವಳಿಯನ್ನು ಪ್ರಸ್ತಾಪಿಸಿದರು. ಅವರ ಅಲ್ಗಾರಿದಮ್ ಸಮಸ್ಯೆಯನ್ನು 2-ಆಯಾಮದ ಘಟಕಗಳಾಗಿ ವಿಭಜಿಸಲು ಮತ್ತು ಆ ಘಟಕಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಒಟ್ಟುಗೂಡಿಸಲು ಕೆಡಿ-ಟ್ರೀಗೆ ಹೋಲುವ ನಿರ್ದಿಷ್ಟ ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಬಳಸುತ್ತದೆ; 2-ಆಯಾಮದ ಸಮಸ್ಯೆಗಳನ್ನು ಸ್ವತಃ ಟ್ರೆಲ್ಲಿಸ್ ರಚನೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಪರಿಹರಿಸಲಾಗುತ್ತದೆ. ಬೆಂಟ್ಲಿಯ ಕ್ರಮಾವಳಿಗಿಂತ ಲಕ್ಷಣರಹಿತವಾಗಿ ವೇಗವಾಗಿದ್ದರೂ, ಅದರ ದತ್ತಾಂಶ ರಚನೆಗಳು ಗಮನಾರ್ಹವಾಗಿ ಹೆಚ್ಚಿನ ಜಾಗವನ್ನು ಬಳಸುತ್ತವೆ, ಆದ್ದರಿಂದ ಇದನ್ನು n ಅಥವಾ d ದೊಡ್ಡದಾದ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಮಾತ್ರ ಬಳಸಲಾಗುತ್ತದೆ. 1998 ರಲ್ಲಿ, ಬೊಗ್ಡನ್ ಕ್ಲೆಬಸ್ ಅವರು ಡಿ 3 ಅಥವಾ 4 ಆಗಿರುವ ಸಾಮಾನ್ಯ ವಿಶೇಷ ಪ್ರಕರಣಗಳಿಗೆ ಅದೇ ಅಸಿಂಪ್ಟೋಟಿಕ್ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯದೊಂದಿಗೆ ಸರಳವಾದ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸಿದರು. 2013 ರಲ್ಲಿ, ತಿಮೋತಿ ಎಮ್. ಚಾನ್ ಸರಳವಾದ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಿದರು, ಇದು ಡೈನಾಮಿಕ್ ಡೇಟಾ ಸ್ಟ್ರಕ್ಚರ್ಗಳ ಅಗತ್ಯವನ್ನು ತಪ್ಪಿಸುತ್ತದೆ ಮತ್ತು ಲಾಗರಿಥಮಿಕ್ ಅಂಶವನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ, ಇದು 3 ರಿಂದ 3 ರವರೆಗೆ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತದೆ. ತಿಳಿದಿರುವ ಮಿತಿಗಳು ಯಾವುದೇ ಡಿಗೆ ತಿಳಿದಿರುವ ಕಡಿಮೆ ಮಿತಿಯು, ಮತ್ತು ಈ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯದೊಂದಿಗೆ ಸೂಕ್ತವಾದ ಕ್ರಮಾವಳಿಗಳು ಡಿ = 1 ಮತ್ತು ಡಿ = 2 ಗೆ ತಿಳಿದಿವೆ. ಚಾನ್ ಅಲ್ಗಾರಿದಮ್ ಡಿ ≤ 3 ಗೆ ಮೇಲಿನ ಮಿತಿಯನ್ನು ಒದಗಿಸುತ್ತದೆ, ಆದ್ದರಿಂದ ಡಿ ≤ 3 ಗೆ, ವೇಗದ ಕ್ರಮಾವಳಿಗಳು ಸಾಧ್ಯವೇ ಅಥವಾ ಪರ್ಯಾಯವಾಗಿ ಬಿಗಿಯಾದ ಕೆಳ ಮಿತಿಯನ್ನು ಸಾಬೀತುಪಡಿಸಬಹುದೇ ಎಂಬುದು ಮುಕ್ತ ಪ್ರಶ್ನೆಯಾಗಿ ಉಳಿದಿದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಅಲ್ಗಾರಿದಮ್ನ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವು ಡಿ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿದೆಯೇ ಎಂಬುದು ಮುಕ್ತವಾಗಿರುತ್ತದೆ. ಜೊತೆಗೆ, ವಿಶೇಷ ಪ್ರಕರಣಗಳನ್ನು ನಿಭಾಯಿಸಬಲ್ಲ ವೇಗದ ಅಲ್ಗಾರಿದಮ್ಗಳಿವೆಯೇ ಎಂಬ ಪ್ರಶ್ನೆಯು ಮುಕ್ತವಾಗಿರುತ್ತದೆ (ಉದಾಹರಣೆಗೆ, ಇನ್ಪುಟ್ ನಿರ್ದೇಶಾಂಕಗಳು ಸೀಮಿತ ವ್ಯಾಪ್ತಿಯೊಳಗೆ ಪೂರ್ಣಾಂಕಗಳಾಗಿದ್ದಾಗ). 1ಡಿ ಕ್ಲೀಯ ಅಳತೆಯ ಸಮಸ್ಯೆಯನ್ನು (ಮಧ್ಯಂತರಗಳ ಒಕ್ಕೂಟ) ಪರಿಹರಿಸಬಹುದು, ಅಲ್ಲಿ p ಎಲ್ಲಾ ಮಧ್ಯಂತರಗಳನ್ನು ಚುಚ್ಚಲು ಅಗತ್ಯವಾದ ಚುಚ್ಚುವ ಬಿಂದುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ (ಸಾಮಾನ್ಯ ಬಿಂದುವಿನಿಂದ ಚುಚ್ಚಿದ ಮಧ್ಯಂತರಗಳ ಒಕ್ಕೂಟವನ್ನು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ತೀವ್ರತೆಯನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಮೂಲಕ ಲೆಕ್ಕ ಹಾಕಬಹುದು). ನಿಯತಾಂಕ p ಎಂಬುದು ಇನ್ಪುಟ್ ಸಂರಚನೆಯನ್ನು ಅವಲಂಬಿಸಿರುವ ಹೊಂದಾಣಿಕೆಯ ನಿಯತಾಂಕವಾಗಿದೆ, ಮತ್ತು ಚುಚ್ಚುವ ಅಲ್ಗಾರಿದಮ್ ಕ್ಲೀಯ ಅಳತೆಯ ಸಮಸ್ಯೆಗೆ ಹೊಂದಾಣಿಕೆಯ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೀಡುತ್ತದೆ. ಕನ್ವೆಕ್ಸ್ ವಾಲ್ಯೂಮ್ ಅಂದಾಜನ್ನು ಸಹ ನೋಡಿ, ಇದು ಕನ್ವೆಕ್ಸ್ ಕಾಯಗಳ ಉಲ್ಲೇಖಗಳು ಮತ್ತು ಹೆಚ್ಚಿನ ಓದುವ ಪ್ರಮುಖ ಪ್ರಬಂಧಗಳಿಗೆ ಪರಿಣಾಮಕಾರಿ ಕ್ರಮಾವಳಿ. .. .. .. .. .. .. ಮಾಧ್ಯಮಿಕ ಸಾಹಿತ್ಯ ಫ್ರಾಂಕೋ ಪಿ. ಪ್ರಿಪರೇಟಾ ಮತ್ತು ಮೈಕೆಲ್ ಐ. ಶಾಮೋಸ್ (1985). ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿ (ಸ್ಪ್ರಿಂಗರ್-ವೆರ್ಲಾಗ್, ಬರ್ಲಿನ್). ಕ್ಲೀಸ್ ಮೆಷರ್ ಪ್ರಾಬ್ಲಮ್, ಪ್ರೊಫೆಸರ್ ಜೆಫ್ ಎರಿಕ್ಸನ್ ಅವರ ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿಯಲ್ಲಿನ ಮುಕ್ತ ಸಮಸ್ಯೆಗಳ ಪಟ್ಟಿಯಿಂದ. (ಕೊನೆಯ ಅಪ್ಡೇಟ್ ಜುಲೈ 31,1998 ಆಗಿದ್ದಾಗ, ನವೆಂಬರ್ 8,2005 ರಂದು ಪ್ರವೇಶಿಸಲಾಗಿದೆ.) ಉಲ್ಲೇಖಗಳು ಗಣಕೀಯ ರೇಖಾಗಣಿತ ಮಾಪನ ಸಿದ್ಧಾಂತ ಗಣಿತದ ಸಮಸ್ಯೆಗಳು