Art gallery problem
ಆರ್ಟ್ ಗ್ಯಾಲರಿ ಸಮಸ್ಯೆ ಅಥವಾ ಮ್ಯೂಸಿಯಂ ಸಮಸ್ಯೆಯು ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿಯಲ್ಲಿ ಚೆನ್ನಾಗಿ ಅಧ್ಯಯನ ಮಾಡಲಾದ ಗೋಚರತೆಯ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಇದು ಈ ಕೆಳಗಿನ ನೈಜ-ಪ್ರಪಂಚದ ಸಮಸ್ಯೆಯಿಂದ ಹುಟ್ಟುತ್ತದೆಃ "ಒಂದು ಆರ್ಟ್ ಗ್ಯಾಲರಿಯಲ್ಲಿ, ಇಡೀ ಗ್ಯಾಲರಿಯನ್ನು ಒಟ್ಟಾಗಿ ವೀಕ್ಷಿಸಬಹುದಾದ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಕಾವಲುಗಾರರು ಎಷ್ಟು?" ಸಮಸ್ಯೆಯ ಜ್ಯಾಮಿತೀಯ ಆವೃತ್ತಿಯಲ್ಲಿ, ಆರ್ಟ್ ಗ್ಯಾಲರಿಯ ವಿನ್ಯಾಸವನ್ನು ಸರಳವಾದ ಬಹುಭುಜಾಕೃತಿಯಿಂದ ಪ್ರತಿನಿಧಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ರಕ್ಷಕವನ್ನು ಬಹುಭುಜಾಕೃತಿಯ ಒಂದು ಬಿಂದುವಿನಿಂದ ಪ್ರತಿನಿಧಿಸಲಾಗುತ್ತದೆ. ಬಹುಭುಜಾಕೃತಿಯ ಪ್ರತಿಯೊಂದು ಬಿಂದುವಿಗೆ, ಮತ್ತು ಮತ್ತು ನಡುವಿನ ರೇಖೆಯ ಭಾಗವು ಬಹುಭುಜಾಕೃತಿಯನ್ನು ಬಿಡದೇ ಇದ್ದರೆ, ಒಂದು ಗುಂಪಿನ ಬಿಂದುಗಳು ಬಹುಭುಜಾಕೃತಿಯನ್ನು ರಕ್ಷಿಸುತ್ತವೆ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ. ಆರ್ಟ್ ಗ್ಯಾಲರಿ ಸಮಸ್ಯೆಯನ್ನು ರೊಬೊಟಿಕ್ಸ್ನಂತಹ ಹಲವಾರು ಡೊಮೇನ್ಗಳಲ್ಲಿ ಅನ್ವಯಿಸಬಹುದು, ಕೃತಕ ಬುದ್ಧಿವಂತಿಕೆಗಳು (AI) ತಮ್ಮ ಸುತ್ತಮುತ್ತಲಿನ ಆಧಾರದ ಮೇಲೆ ಚಲನೆಗಳನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಬೇಕಾಗುತ್ತದೆ. ಈ ಸಮಸ್ಯೆಯನ್ನು ಅನ್ವಯಿಸುವ ಇತರ ಕ್ಷೇತ್ರಗಳೆಂದರೆ, ಚಿತ್ರ ಸಂಪಾದನೆ, ವೇದಿಕೆಯ ಬೆಳಕಿನ ಸಮಸ್ಯೆಗಳು ಅಥವಾ ನೈಸರ್ಗಿಕ ವಿಕೋಪಗಳ ಎಚ್ಚರಿಕೆಗಾಗಿ ಮೂಲಸೌಕರ್ಯಗಳ ಸ್ಥಾಪನೆ. ಎರಡು ಆಯಾಮಗಳು ಮೂಲ ಸಮಸ್ಯೆಯ ಹಲವಾರು ವ್ಯತ್ಯಾಸಗಳಿವೆ, ಇದನ್ನು ಆರ್ಟ್ ಗ್ಯಾಲರಿ ಸಮಸ್ಯೆ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ. ಕೆಲವು ಆವೃತ್ತಿಗಳಲ್ಲಿ ಕಾವಲುಗಾರರನ್ನು ಪರಿಧಿಯವರೆಗೆ ಅಥವಾ ಬಹುಭುಜಾಕೃತಿಯ ಶೃಂಗಗಳವರೆಗೆ ನಿರ್ಬಂಧಿಸಲಾಗಿದೆ. ಕೆಲವು ಆವೃತ್ತಿಗಳಿಗೆ ಕೇವಲ ಪರಿಧಿಯ ಅಥವಾ ಪರಿಧಿಯ ಉಪವಿಭಾಗವನ್ನು ರಕ್ಷಿಸುವ ಅಗತ್ಯವಿರುತ್ತದೆ. ಕಾವಲುಗಾರರನ್ನು ಶೃಂಗಗಳ ಮೇಲೆ ಇರಿಸಬೇಕಾದ ಮತ್ತು ಶೃಂಗಗಳನ್ನು ಮಾತ್ರ ರಕ್ಷಿಸಬೇಕಾದ ಆವೃತ್ತಿಯನ್ನು ಪರಿಹರಿಸುವುದು ಬಹುಭುಜಾಕೃತಿಯ ಗೋಚರತೆಯ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಪ್ರಾಬಲ್ಯದ ಸೆಟ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವುದಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ಚಾವಟಲ್ನ ಆರ್ಟ್ ಗ್ಯಾಲರಿ ಪ್ರಮೇಯವಾದ ಚಾವಟಲ್ನ ಆರ್ಟ್ ಗ್ಯಾಲರಿ ಪ್ರಮೇಯವು, ವಕ್ಲಾವ್ ಚಾವಟಲ್ನ ಹೆಸರಿನಿಂದ ಕರೆಯಲ್ಪಟ್ಟಿದೆ, ಇದು ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಕಾವಲುಗಾರರ ಮೇಲೆ ಮೇಲಿನ ಮಿತಿಯನ್ನು ನೀಡುತ್ತದೆ. ಇದು ಹೀಗೆ ಹೇಳುತ್ತದೆಃ "ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಸರಳ ಬಹುಭುಜಾಕೃತಿಯನ್ನು ರಕ್ಷಿಸಲು, ಕಾವಲುಗಾರರು ಯಾವಾಗಲೂ ಸಾಕಾಗುತ್ತಾರೆ ಮತ್ತು ಕೆಲವೊಮ್ಮೆ ಅಗತ್ಯವಾಗಿರುತ್ತಾರೆ". ಎಷ್ಟು ಶೃಂಗಗಳು/ಕಾವಲುಗಾರರು/ಕಾವಲುಗಾರರು ಬೇಕಾಗಿದ್ದಾರೆ ಎಂಬ ಪ್ರಶ್ನೆಯನ್ನು 1973ರಲ್ಲಿ ವಿಕ್ಟರ್ ಕ್ಲೀ ಅವರು ಚ್ವಾಟಲ್ಗೆ ಕೇಳಿದರು. ಸ್ವಲ್ಪ ಸಮಯದ ನಂತರ ಚಾವಟಲ್ ಅದನ್ನು ಸಾಬೀತುಪಡಿಸಿದರು. ಚಾವಟಲ್ನ ಪುರಾವೆಯನ್ನು ನಂತರ ಸ್ಟೀವ್ ಫಿಸ್ಕ್ ಅವರು 3-ಬಣ್ಣದ ವಾದದ ಮೂಲಕ ಸರಳೀಕರಿಸಿದರು. ಚಾವಟಲ್ ಹೆಚ್ಚು ಜ್ಯಾಮಿತೀಯ ವಿಧಾನವನ್ನು ಹೊಂದಿದ್ದರೆ, ಫಿಸ್ಕ್ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಿಂದ ಪ್ರಸಿದ್ಧವಾದ ಫಲಿತಾಂಶಗಳನ್ನು ಬಳಸುತ್ತದೆ. ಫಿಸ್ಕ್ನ ಸಣ್ಣ ಪುರಾವೆ ಸ್ಟೀವ್ ಫಿಸ್ಕ್ನ ಪುರಾವೆಯು ಎಷ್ಟು ಚಿಕ್ಕದಾಗಿದೆ ಮತ್ತು ಸೊಗಸಾದದ್ದಾಗಿದೆ ಎಂದರೆ ಅದನ್ನು ಪುಸ್ತಕದ ಪುರಾವೆಗಳಲ್ಲಿ ಸೇರಿಸಲು ಆಯ್ಕೆ ಮಾಡಲಾಗಿದೆ. ಪುರಾವೆಯು ಈ ಕೆಳಗಿನಂತೆ ಹೋಗುತ್ತದೆಃ ಮೊದಲನೆಯದಾಗಿ, ಬಹುಭುಜಾಕೃತಿಯು ತ್ರಿಕೋನವಾಗಿದೆ (ಹೆಚ್ಚುವರಿ ಶೃಂಗಗಳನ್ನು ಸೇರಿಸದೆ), ಇದು ಸಾಧ್ಯ, ಏಕೆಂದರೆ ತ್ರಿಕೋನಗಳ ಅಸ್ತಿತ್ವವು ಕೆಲವು ಪರಿಶೀಲಿಸಿದ ಪರಿಸ್ಥಿತಿಗಳಲ್ಲಿ ಸಾಬೀತಾಗಿದೆ. ಪರಿಣಾಮವಾಗಿ ತ್ರಿಕೋನ ರೇಖಾಚಿತ್ರದ ಶೃಂಗಗಳು 3-ಬಣ್ಣದದ್ದಾಗಿರಬಹುದು. ಸ್ಪಷ್ಟವಾಗಿ, 3-ಬಣ್ಣದ ಅಡಿಯಲ್ಲಿ, ಪ್ರತಿ ತ್ರಿಕೋನವು ಎಲ್ಲಾ ಮೂರು ಬಣ್ಣಗಳನ್ನು ಹೊಂದಿರಬೇಕು. ಯಾವುದೇ ಒಂದು ಬಣ್ಣದ ಶೃಂಗಗಳು ಮಾನ್ಯವಾದ ಕಾವಲು ಗುಂಪನ್ನು ರೂಪಿಸುತ್ತವೆ, ಏಕೆಂದರೆ ಬಹುಭುಜಾಕೃತಿಯ ಪ್ರತಿಯೊಂದು ತ್ರಿಕೋನವು ಆ ಬಣ್ಣದೊಂದಿಗೆ ಅದರ ಶೃಂಗದಿಂದ ರಕ್ಷಿಸಲ್ಪಡುತ್ತದೆ. ಮೂರು ಬಣ್ಣಗಳು ಬಹುಭುಜಾಕೃತಿಯ n ಶೃಂಗಗಳನ್ನು ವಿಭಜಿಸುವುದರಿಂದ, ಕಡಿಮೆ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಬಣ್ಣವು ಹೆಚ್ಚಿನ ಗಾರ್ಡ್ಗಳೊಂದಿಗೆ ಮಾನ್ಯವಾದ ಗಾರ್ಡ್ ಸೆಟ್ ಅನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತದೆ. ಪುರಾವೆಯ ವಿವರಣೆ ಪುರಾವೆಯನ್ನು ವಿವರಿಸಲು, ನಾವು ಕೆಳಗಿನ ಬಹುಭುಜಾಕೃತಿಯನ್ನು ಪರಿಗಣಿಸುತ್ತೇವೆ. ಬಹುಭುಜಾಕೃತಿಯನ್ನು ತ್ರಿಕೋನಗೊಳಿಸುವುದು ಮೊದಲ ಹಂತವಾಗಿದೆ (ಚಿತ್ರ 1 ನೋಡಿ). ನಂತರ, ಒಬ್ಬರು ಸರಿಯಾದ ಬಣ್ಣವನ್ನು ಅನ್ವಯಿಸುತ್ತಾರೆ (ಚಿತ್ರ 2) ಮತ್ತು ಕೆಂಪು, ನೀಲಿ ಮತ್ತು ಹಸಿರು ಶೃಂಗಗಳಿವೆ ಎಂದು ಗಮನಿಸುತ್ತಾರೆ. ಕಡಿಮೆ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಬಣ್ಣವು ನೀಲಿ ಅಥವಾ ಕೆಂಪು ಬಣ್ಣದ್ದಾಗಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ಬಹುಭುಜಾಕೃತಿಯನ್ನು ಕಾವಲುಗಾರರಿಂದ ಮುಚ್ಚಬಹುದು (ಚಿತ್ರ 3). ಇದು ಆರ್ಟ್ ಗ್ಯಾಲರಿ ಪ್ರಮೇಯವನ್ನು ಒಪ್ಪುತ್ತದೆ, ಏಕೆಂದರೆ ಬಹುಭುಜಾಕೃತಿಯು ಶೃಂಗಗಳನ್ನು ಹೊಂದಿದೆ, ಮತ್ತು. ಸಾಮಾನ್ಯೀಕರಣಗಳು ಬಹುಭುಜಾಕೃತಿಯ ಹೊರಗಿನ ಯಾವುದೇ ಹಂತದಲ್ಲಿ ಮೂಲೆಗಳಲ್ಲಿ ಕಾವಲುಗಾರರಿಗೆ ನಿರ್ಬಂಧವನ್ನು ಸಡಿಲಗೊಳಿಸಿದರೆ ಚಾವಟಲ್ನ ಮೇಲಿನ ಮಿತಿಯು ಮಾನ್ಯವಾಗಿರುತ್ತದೆ. ಮೂಲ ಕಲಾ-ಗ್ಯಾಲರಿ ಪ್ರಮೇಯದ ಹಲವಾರು ಇತರ ಸಾಮಾನ್ಯೀಕರಣಗಳು ಮತ್ತು ವಿಶೇಷತೆಗಳಿವೆ. ಉದಾಹರಣೆಗೆ, ಲಂಬಭುಜಾಕೃತಿಯ ಬಹುಭುಜಾಕೃತಿಗಳಿಗೆ, ಅವುಗಳ ಅಂಚುಗಳು/ಗೋಡೆಗಳು ಸಮಕೋಣೆಯಲ್ಲಿ ಸಂಧಿಸಿದರೆ, ಕಾವಲುಗಾರರು ಮಾತ್ರ ಬೇಕಾಗುತ್ತಾರೆ. ಈ ಫಲಿತಾಂಶಕ್ಕೆ ಕನಿಷ್ಠ ಮೂರು ವಿಭಿನ್ನ ಪುರಾವೆಗಳಿವೆ, ಅವುಗಳಲ್ಲಿ ಯಾವುದೂ ಸರಳವಾಗಿಲ್ಲಃ ಕಾನ್, ಕ್ಲಾವ್ ಮತ್ತು ಕ್ಲೈಟ್ಮನ್ ಅವರಿಂದ; ಲುಬಿವ್ ಅವರಿಂದ; ಮತ್ತು ಸ್ಯಾಕ್ ಮತ್ತು ಟೌಸೈಂಟ್ ಅವರಿಂದ. ಒಂದು ಸಂಬಂಧಿತ ಸಮಸ್ಯೆಯು ಒಂದು ಅನಿಯಂತ್ರಿತ ಬಹುಭುಜಾಕೃತಿಯ ("ಕೋಟೆ ಸಮಸ್ಯೆ") ಹೊರಭಾಗವನ್ನು ಆವರಿಸಲು ಕಾವಲುಗಾರರ ಸಂಖ್ಯೆಯನ್ನು ಕೇಳುತ್ತದೆಃ ಕಾವಲುಗಾರರನ್ನು ಬಹುಭುಜಾಕೃತಿಯ ಗಡಿಯಲ್ಲಿ ಇರಿಸಿದರೆ ಕೆಲವೊಮ್ಮೆ ಅಗತ್ಯವಾಗಿರುತ್ತದೆ ಮತ್ತು ಯಾವಾಗಲೂ ಸಾಕಾಗುತ್ತದೆ, ಆದರೆ ಕೆಲವೊಮ್ಮೆ ಅಗತ್ಯವಾಗಿರುತ್ತದೆ ಮತ್ತು ಬಹುಭುಜಾಕೃತಿಯ ಹೊರಭಾಗದಲ್ಲಿ ಎಲ್ಲಿಯಾದರೂ ಕಾವಲುಗಾರರನ್ನು ಇರಿಸಿದರೆ ಯಾವಾಗಲೂ ಸಾಕಾಗುತ್ತದೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಅನಂತ ಬಾಹ್ಯವು ಸೀಮಿತ ಒಳಭಾಗಕ್ಕಿಂತ ಹೆಚ್ಚು ಸವಾಲಿನದ್ದಾಗಿದೆ. ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಆರ್ಟ್ ಗ್ಯಾಲರಿ ಸಮಸ್ಯೆಯ ನಿರ್ಧಾರ ಸಮಸ್ಯೆಯ ಆವೃತ್ತಿಗಳಲ್ಲಿ, ಒಂದನ್ನು ಬಹುಭುಜಾಕೃತಿ ಮತ್ತು ಕೆ ಸಂಖ್ಯೆ ಎರಡನ್ನೂ ಇನ್ಪುಟ್ ಆಗಿ ನೀಡಲಾಗುತ್ತದೆ, ಮತ್ತು ಬಹುಭುಜಾಕೃತಿಯನ್ನು ಕೆ ಅಥವಾ ಕಡಿಮೆ ಗಾರ್ಡ್ಗಳೊಂದಿಗೆ ರಕ್ಷಿಸಬಹುದೇ ಎಂದು ನಿರ್ಧರಿಸಬೇಕು. ಈ ಸಮಸ್ಯೆಯು ಪೂರ್ಣಗೊಂಡಿದೆ, ಹಾಗೆಯೇ ಬಹುಭುಜಾಕೃತಿಯ ಅಂಚುಗಳಿಗೆ ಕಾವಲುಗಾರರನ್ನು ನಿರ್ಬಂಧಿಸಿರುವ ಆವೃತ್ತಿಯೂ ಆಗಿದೆ. ಇದಲ್ಲದೆ, ಹೆಚ್ಚಿನ ಇತರ ಪ್ರಮಾಣಿತ ಮಾರ್ಪಾಡುಗಳು (ಉದಾಹರಣೆಗೆ ಕಾವಲು ಸ್ಥಳಗಳನ್ನು ಶೃಂಗಗಳಿಗೆ ಸೀಮಿತಗೊಳಿಸುವುದು) ಎನ್. ಪಿ.-ಗಟ್ಟಿಯಾಗಿರುತ್ತವೆ. ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಗಾರ್ಡ್ಗಳ ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳಿಗೆ ಸಂಬಂಧಿಸಿದಂತೆ, ಸಮಸ್ಯೆಯನ್ನು ಎ. ಪಿ. ಎಕ್ಸ್-ಹಾರ್ಡ್ ಎಂದು ಸಾಬೀತುಪಡಿಸಿತು, ಇದು ಬಹುಪದೀಯ ಸಮಯ ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳಿಂದ ಕೆಲವು ಸ್ಥಿರ ಸ್ಥಿರಾಂಕಗಳಿಗಿಂತ ಉತ್ತಮವಾದ ಯಾವುದೇ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಸಾಧಿಸುವ ಸಾಧ್ಯತೆಯಿಲ್ಲ ಎಂದು ಸೂಚಿಸುತ್ತದೆ. ಇನ್ಪುಟ್ ಬಹುಭುಜಾಕೃತಿಯನ್ನು ಕನ್ವೆಕ್ಸ್ ಉಪಪ್ರದೇಶಗಳಾಗಿ ವಿಂಗಡಿಸುವ ಮೂಲಕ ಮತ್ತು ನಂತರ ಸಮಸ್ಯೆಯನ್ನು ಸೆಟ್ ಕವರ್ ಸಮಸ್ಯೆಯಾಗಿ ಕಡಿಮೆ ಮಾಡುವ ಮೂಲಕ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಶೃಂಗ ರಕ್ಷಕಗಳಿಗೆ ಲಾಗರಿಥಮಿಕ್ ಅಂದಾಜನ್ನು ಸಾಧಿಸಬಹುದು ಎಂದು ತೋರಿಸಿದೆ. ತೋರಿಸಿದಂತೆ, ಆರ್ಟ್ ಗ್ಯಾಲರಿ ಸಮಸ್ಯೆಯಿಂದ ಪಡೆದ ಸೆಟ್ ವ್ಯವಸ್ಥೆಯು ವಿಸಿ ಆಯಾಮವನ್ನು ಸೀಮಿತಗೊಳಿಸಿದೆ, ಇದು ε-ನೆಟ್ಗಳ ಆಧಾರದ ಮೇಲೆ ಸೆಟ್ ಕವರ್ ಅಲ್ಗಾರಿದಮ್ಗಳ ಅನ್ವಯವನ್ನು ಅನುಮತಿಸುತ್ತದೆ, ಇದರ ಅಂದಾಜು ಅನುಪಾತವು ಬಹುಭುಜಾಕೃತಿಯ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಗಿಂತ ಸೂಕ್ತ ಸಂಖ್ಯೆಯ ಗಾರ್ಡ್ಗಳ ಲಾಗರಿಥಮ್ ಆಗಿದೆ. ಅನಿಯಂತ್ರಿತ ಕಾವಲುಗಾರರಿಗೆ, ಅನಂತ ಸಂಖ್ಯೆಯ ಸಂಭಾವ್ಯ ಕಾವಲು ಸ್ಥಾನಗಳು ಸಮಸ್ಯೆಯನ್ನು ಇನ್ನಷ್ಟು ಕಷ್ಟಕರವಾಗಿಸುತ್ತವೆ. ಆದಾಗ್ಯೂ, ಕಾವಲುಗಾರರನ್ನು ಸೂಕ್ಷ್ಮ ಗ್ರಿಡ್ನಲ್ಲಿ ಮಲಗುವುದನ್ನು ನಿರ್ಬಂಧಿಸುವ ಮೂಲಕ, ಕೆಲವು ಸೌಮ್ಯವಾದ ಹೆಚ್ಚುವರಿ ಊಹೆಗಳ ಅಡಿಯಲ್ಲಿ ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾದ ಲಾಗರಿಥಮಿಕ್ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪಡೆಯಬಹುದು. ಆದಾಗ್ಯೂ, ಚ್ವಾಟಲ್ನ ಮೇಲಿನ ಮಿತಿಯೊಂದಿಗೆ ಹೊಂದಿಕೆಯಾಗುವ ಹೆಚ್ಚಿನ ಶೃಂಗ ರಕ್ಷಾಕವಚಗಳ ಗುಂಪನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪರಿಣಾಮಕಾರಿ ಕ್ರಮಾವಳಿಗಳು ಹೆಸರುವಾಸಿಯಾಗಿವೆ. ಈ ಕಾವಲುಗಾರರ ನಿಯೋಜನೆಯನ್ನು ಓ (ಎನ್ ಲಾಗ್ ಎನ್) ಸಮಯದಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು ಎಂದು ಸಾಬೀತಾಯಿತು, ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, ವಿಭಜನೆ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳುವ ಅಲ್ಗಾರಿದಮ್ನ ಮೂಲಕ. ಫಿಸ್ಕ್ನ ಸಣ್ಣ ಪುರಾವೆ ಮತ್ತು ಬರ್ನಾರ್ಡ್ ಚಾಝೆಲ್ಲೆಯ ರೇಖೀಯ ಸಮಯ ಸಮತಲ ತ್ರಿಕೋನ ಕ್ರಮಾವಳಿಯನ್ನು ಬಳಸಿಕೊಂಡು ರೇಖೀಯ ಸಮಯ ಕ್ರಮಾವಳಿಯನ್ನು ನೀಡಿದರು. ರಂಧ್ರಗಳನ್ನು ಹೊಂದಿರದ ಸರಳ ಬಹುಭುಜಾಕೃತಿಗಳಿಗೆ, ಶೃಂಗ ಮತ್ತು ಅಂಚಿನ ಕಾವಲುಗಳಿಗಾಗಿ ಸ್ಥಿರವಾದ ಅಂಶ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ನ ಅಸ್ತಿತ್ವವನ್ನು ಘೋಷ್ ಊಹಿಸಿದ್ದಾರೆ. ಘೋಷ್ ಅವರ ಊಹೆಯು ಆರಂಭದಲ್ಲಿ ಸರಳ ಬಹುಭುಜಾಕೃತಿಗಳ ಎರಡು ವಿಶೇಷ ಉಪವರ್ಗಗಳಲ್ಲಿ ಶೃಂಗದ ಕಾವಲುಗಾರರಿಗೆ ನಿಜವೆಂದು ತೋರಿಸಲಾಗಿದೆ. ಮೊನೊಟೋನ್ ಬಹುಭುಜಾಕೃತಿಗಳು ಮತ್ತು ಬಹುಭುಜಾಕೃತಿಗಳು ಒಂದು ತುದಿಯಿಂದ ದುರ್ಬಲವಾಗಿ ಗೋಚರಿಸುತ್ತವೆ. ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಮೊನೊಟೋನ್ ಬಹುಭುಜಾಕೃತಿಯ ಒಂದು ಶೃಂಗ ರಕ್ಷಕವನ್ನು ಗಣಿಸುವ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಲಾಯಿತು, ಅಂದರೆ ಕಾವಲುಗಾರನ ಗುಂಪಿನ ಗಾತ್ರವು ಶೃಂಗ ರಕ್ಷಕಗಳ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ 30 ಪಟ್ಟು ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ಒಂದು ತುದಿಯಿಂದ ದುರ್ಬಲವಾಗಿ ಗೋಚರಿಸುವ ಸರಳವಾದ ಬಹುಭುಜಾಕೃತಿಯ ಒಂದು ಶೃಂಗ ರಕ್ಷಕವನ್ನು O (n2) ಸಮಯದಲ್ಲಿ ಗಣಿಸುವ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಲಾಯಿತು, ಅಂದರೆ ಕಾವಲುಗಾರನ ಗುಂಪಿನ ಗಾತ್ರವು ಶೃಂಗ ರಕ್ಷಕಗಳ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ 6 ಪಟ್ಟು ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ತರುವಾಯ, ಶೃಂಗ ರಕ್ಷಾಕವಚಗಳು ಮತ್ತು ಅಂಚಿನ ರಕ್ಷಾಕವಚಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಸಾಮಾನ್ಯ ಸರಳ ಬಹುಭುಜಾಕೃತಿಗಳನ್ನು ರಕ್ಷಿಸಲು ಸ್ಥಿರವಾದ ಅಂಶ ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುವ ಮೂಲಕ ಊಹೆಯನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ಇತ್ಯರ್ಥಪಡಿಸಲಾಗಿದೆ ಎಂದು ಹೇಳಲಾಗಿದೆ. ಒಂದು ತುದಿಯಿಂದ ದುರ್ಬಲವಾಗಿ ಗೋಚರಿಸುವ ಸರಳ ಬಹುಭುಜಾಕೃತಿಗಳ ಉಪವರ್ಗವನ್ನು ಕಾಪಾಡುವ ಶೃಂಗಕ್ಕೆ, ಬಹುಪದ-ಸಮಯದ ಅಂದಾಜು ಯೋಜನೆಯನ್ನು ಅವರು ಪ್ರಸ್ತಾಪಿಸಿದರು. ವೆರ್ಟೆಕ್ಸ್ ಗಾರ್ಡ್ಗಳಿಗಾಗಿ ನಿಖರವಾದ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸಲಾಗಿದೆ. ಸಾವಿರಾರು ಶೃಂಗಗಳಿಗೆ ಸಂಬಂಧಿಸಿದ ನಿದರ್ಶನಗಳಿಗೂ ಸಹ ತುಲನಾತ್ಮಕವಾಗಿ ಸಣ್ಣ ಗಣನೆಯ ಸಮಯಗಳಲ್ಲಿ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರಗಳನ್ನು ಕಂಡುಹಿಡಿಯಬಹುದು ಎಂದು ತೋರಿಸುವ ಹಲವಾರು ವರ್ಗದ ಬಹುಭುಜಾಕೃತಿಗಳೊಂದಿಗೆ ಲೇಖಕರು ವ್ಯಾಪಕವಾದ ಗಣನೆಯ ಪ್ರಯೋಗಗಳನ್ನು ನಡೆಸಿದರು. ಈ ನಿದರ್ಶನಗಳಿಗೆ ಇನ್ಪುಟ್ ಡೇಟಾ ಮತ್ತು ಅತ್ಯುತ್ತಮ ಪರಿಹಾರಗಳು ಡೌನ್ಲೋಡ್ಗೆ ಲಭ್ಯವಿವೆ. ಮೂರು ಆಯಾಮಗಳು ಒಂದು ವಸ್ತುಸಂಗ್ರಹಾಲಯವನ್ನು ಮೂರು ಆಯಾಮಗಳಲ್ಲಿ ಪಾಲಿಹೆಡ್ರನ್ ಆಗಿ ಪ್ರತಿನಿಧಿಸಿದರೆ, ಪ್ರತಿ ತುದಿಯಲ್ಲಿ ಕಾವಲುಗಾರನನ್ನು ಇರಿಸುವುದರಿಂದ ಎಲ್ಲಾ ವಸ್ತುಸಂಗ್ರಹಾಲಯವು ವೀಕ್ಷಣೆಯಲ್ಲಿದೆ ಎಂದು ಖಚಿತಪಡಿಸುವುದಿಲ್ಲ. ಪಾಲಿಹೆಡ್ರನ್ನ ಎಲ್ಲಾ ಮೇಲ್ಮೈಯನ್ನು ಸಮೀಕ್ಷೆ ಮಾಡಲಾಗುತ್ತದೆಯಾದರೂ, ಕೆಲವು ಪಾಲಿಹೆಡ್ರಾಗಳಿಗೆ ಒಳಭಾಗದಲ್ಲಿ ಕಣ್ಗಾವಲಿನಲ್ಲಿರದ ಬಿಂದುಗಳಿವೆ. ಆರ್ಟ್ ಗ್ಯಾಲರಿ ಸಮಸ್ಯೆಯ ಸಂಭಾವ್ಯ ಬಳಕೆಯ ಸನ್ನಿವೇಶಗಳು ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಕ್ಯಾಮೆರಾಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಕ್ಯಾಮೆರಾಗಳ ದೃಷ್ಟಿಯಿಂದ ದೊಡ್ಡ ಪ್ರದೇಶವನ್ನು ಆವರಿಸುವ ಉದ್ದೇಶವಿದ್ದಾಗ ಆರ್ಟ್ ಗ್ಯಾಲರಿ ಸಮಸ್ಯೆಯನ್ನು ಅನೇಕ ಕ್ಯಾಮೆರಾಗಳನ್ನು ಇರಿಸಲು ಬಳಸಬಹುದು. ಸ್ಟಾರ್-ಆಕಾರದ ಬಹುಭುಜಾಕೃತಿಯ ನಕ್ಷತ್ರ ಬಹುಭುಜಾಕೃತಿಯೊಂದಿಗೆ ಒಂದು ಆಯತಾಕಾರದ ಬಹುಭುಜಾಕೃತಿಯನ್ನು ಮುಚ್ಚುವುದನ್ನು ಸಹ ನೋಡಿ, ಇದು ಬಹುಭುಜಾಕೃತಿಯ ಒಂದು ವರ್ಗವಾಗಿದ್ದು, ಇದಕ್ಕಾಗಿ ಆರ್ಟ್ ಗ್ಯಾಲರಿಯ ಸಮಸ್ಯೆಯನ್ನು ಒಂದೇ ಗಾರ್ಡ್ನೊಂದಿಗೆ ಪರಿಹರಿಸಬಹುದು. ಬೆಳಕಿನ ಸಮಸ್ಯೆಃ ಗೋಡೆಗಳು ಪ್ರತಿಬಿಂಬಿತವಾಗಿದ್ದರೆ ಒಂದೇ ಗಾರ್ಡು ಸಾಕಾಗುತ್ತದೆಯೇ? ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖ ಮೂಲಗಳು. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ಗಣಕೀಯ ರೇಖಾಗಣಿತ ಪುರಾವೆಗಳನ್ನು ಹೊಂದಿರುವ ಲೇಖನಗಳು ಸಮಸ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಬಹುಭುಜಾಕೃತಿಗಳು