Kinetic convex hull
ಚಲನಶೀಲ ಕನ್ವೆಕ್ಸ್ ಹಲ್ ದತ್ತಾಂಶ ರಚನೆಯು ಚಲನಶೀಲ ದತ್ತಾಂಶ ರಚನೆಯಾಗಿದ್ದು, ಇದು ನಿರಂತರವಾಗಿ ಚಲಿಸುವ ಬಿಂದುಗಳ ಗುಂಪಿನ ಕನ್ವೆಕ್ಸ್ ಹಲ್ ಅನ್ನು ನಿರ್ವಹಿಸುತ್ತದೆ. ಇದನ್ನು ಕ್ರಿಯಾತ್ಮಕ ಕನ್ವೆಕ್ಸ್ ಹಲ್ ದತ್ತಾಂಶ ರಚನೆಗಳಿಂದ ಪ್ರತ್ಯೇಕಿಸಬೇಕು, ಇದು ನಿರಂತರ ಚಲನೆಯ ಬದಲು ಬಿಂದುಗಳ ಅಳವಡಿಕೆ ಅಥವಾ ಅಳಿಸುವಿಕೆಯಂತಹ ಪ್ರತ್ಯೇಕ ಬದಲಾವಣೆಗಳಿಗೆ ಒಳಗಾಗುವ ಬಿಂದುಗಳನ್ನು ನಿರ್ವಹಿಸುತ್ತದೆ. 2ಡಿ ಪ್ರಕರಣವು 2-ಆಯಾಮದ ಕೈನೆಟಿಕ್ ಕನ್ವೆಕ್ಸ್ ಹಲ್ ಸಮಸ್ಯೆಗೆ ಅತ್ಯಂತ ಪ್ರಸಿದ್ಧವಾದ ದತ್ತಾಂಶ ರಚನೆಯು ಬಾಸ್ಚ್, ಗುಯಿಬಾಸ್ ಮತ್ತು ಹರ್ಷ್ಬರ್ಗರ್ ಅವರಿಂದ ಮಾಡಲ್ಪಟ್ಟಿದೆ. ಈ ದತ್ತಾಂಶ ರಚನೆಯು ಪ್ರತಿಕ್ರಿಯಾತ್ಮಕವಾಗಿದೆ, ಪರಿಣಾಮಕಾರಿಯಾಗಿದೆ, ಸಾಂದ್ರವಾಗಿದೆ ಮತ್ತು ಸ್ಥಳೀಯವಾಗಿದೆ. ದತ್ತಾಂಶ ರಚನೆಯು ಬಿಂದುಗಳ ಗುಂಪಿನ ಕನ್ವೆಕ್ಸ್ ಹಲ್ನ ಡ್ಯುಯಲ್ ಎಂದರೆ ರೇಖೆಗಳ ಡ್ಯುಯಲ್ ಗುಂಪಿನ ಮೇಲಿನ ಮತ್ತು ಕೆಳಗಿನ ಲಕೋಟೆಗಳು. ಆದ್ದರಿಂದ, ಚಲಿಸುವ ರೇಖೆಗಳ ಗುಂಪಿನ ಮೇಲಿನ ಮತ್ತು ಕೆಳಗಿನ ಲಕೋಟೆಯನ್ನು ನಿರ್ವಹಿಸುವುದು ಚಲಿಸುವ ಬಿಂದುಗಳ ಗುಂಪಿನ ಕನ್ವೆಕ್ಸ್ ಹಲ್ ಅನ್ನು ನಿರ್ವಹಿಸುವುದಕ್ಕೆ ಸಮಾನವಾಗಿದೆ. ಮೇಲಿನ ಮತ್ತು ಕೆಳಗಿನ ಲಕೋಟೆಗಳನ್ನು ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳುವುದು ಸಮಾನ ಸಮಸ್ಯೆಗಳಾಗಿವೆ, ಆದ್ದರಿಂದ ರೇಖೆಗಳ ಗುಂಪಿನ ಮೇಲಿನ ಲಕೋಟೆಯನ್ನು ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳುವುದು ಚಲಿಸುವ ಬಿಂದುಗಳ ಗುಂಪಿನ ಕನ್ವೆಕ್ಸ್ ಹಲ್ ಅನ್ನು ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳುವುದಕ್ಕೆ ಸಮಾನವಾಗಿದೆ. ಸ್ಥಿರ ರೇಖೆಗಳ ಗುಂಪಿನ ಮೇಲಿನ ಲಕೋಟೆಯನ್ನು ವಿಭಜನೆ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳುವ ಅಲ್ಗಾರಿದಮ್ ಬಳಸಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು, ಇದು ರೇಖೆಗಳನ್ನು ಸಮಾನ ಗಾತ್ರದ ಎರಡು ಸೆಟ್ಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ, ಅವುಗಳ ಮೇಲಿನ ಲಕೋಟೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಎರಡು ಸೆಟ್ಗಳಲ್ಲಿ ಪುನರಾವರ್ತಿತವಾಗಿ ಕರೆ ಮಾಡುತ್ತದೆ ಮತ್ತು ನಂತರ ಎರಡು ಪರಿಣಾಮವಾಗಿ ಮೇಲಿನ ಲಕೋಟೆಯನ್ನು ವಿಲೀನಗೊಳಿಸುತ್ತದೆ. ವಿಲೀನ ಹಂತವನ್ನು ಲಂಬವಾದ ಲೈನ್ ಸ್ವೀಪ್ ಬಳಸಿ ನಡೆಸಲಾಗುತ್ತದೆ. ಮೊದಲ ಗುಂಪಿನ ಅಂಕಗಳನ್ನು ನೀಲಿ ಮತ್ತು ಎರಡನೇ ಗುಂಪಿನ ಅಂಕಗಳನ್ನು ಕೆಂಪು ಎಂದು ಕರೆಯಿರಿ. ಮೇಲಿನ ಲಕೋಟೆಗಳನ್ನು ವಿಲೀನಗೊಳಿಸುವ ಸ್ಟ್ಯಾಂಡರ್ಡ್ ಲೈನ್ ಸ್ವೀಪ್ ಅಲ್ಗಾರಿದಮ್ ಕೆಂಪು ಮತ್ತು ನೀಲಿ ಮೇಲಿನ ಲಕೋಟೆಗಳ ಎಲ್ಲಾ ಶೃಂಗಗಳನ್ನು ಎಡದಿಂದ ಬಲಕ್ಕೆ ತಿರುಗಿಸುತ್ತದೆ. ಇತ್ತೀಚೆಗೆ ಎದುರಾದ ಕೆಂಪು ಮತ್ತು ನೀಲಿ ಬಿಂದುಗಳನ್ನು ಲೈನ್ ಸ್ವೀಪ್ಗಳಾಗಿ ನಿರ್ವಹಿಸಲಾಗುತ್ತದೆ. ಒಂದು ಬಿಂದುವನ್ನು ಎದುರಿಸಿದಾಗ, ವಿರುದ್ಧ ಬಣ್ಣದ ಕೊನೆಯ ಎದುರಾದ ಬಿಂದುವನ್ನು ಅನುಸರಿಸಿ ಬಿಂದುವು ವಿಭಾಗದ ಮೇಲೆ ಅಥವಾ ಕೆಳಗೆ ಇದೆಯೇ ಎಂದು ಅಲ್ಗಾರಿದಮ್ ಪರಿಶೀಲಿಸುತ್ತದೆ. ಅದು ಮೇಲಾಗಿದ್ದರೆ, ಆ ಬಿಂದುವನ್ನು ವಿಲೀನಗೊಂಡ ಮೇಲಿನ ಲಕೋಟೆಗೆ ಸೇರಿಸಲಾಗುತ್ತದೆ. ಇದು ಕೊನೆಯ ಸೇರ್ಪಡೆಗೊಂಡ ಬಿಂದುವಿಗಿಂತ ಬೇರೆ ಬಣ್ಣದಲ್ಲಿದ್ದರೆ, ಕೆಂಪು ಮತ್ತು ನೀಲಿ ಲಕೋಟೆಗಳು ದಾಟಿವೆ, ಆದ್ದರಿಂದ ಛೇದಕ ಬಿಂದುವನ್ನು ಸಹ ವಿಲೀನಗೊಂಡ ಮೇಲಿನ ಲಕೋಟೆಗೆ ಸೇರಿಸಲಾಗುತ್ತದೆ. ಈ ಕ್ರಮಾವಳಿಯಿಂದ ಉಂಟಾಗುವ ಅಂಚುಗಳು ಮತ್ತು ಶೃಂಗಗಳ ಅನುಕ್ರಮವು ಬಿಂದುಗಳ ಕ್ರಮ ಮತ್ತು ರೇಖೆ-ಬಿಂದುವಿನ ಹೋಲಿಕೆಗಳ ಫಲಿತಾಂಶಗಳ ಮೇಲೆ ಮಾತ್ರ ಅವಲಂಬಿತವಾಗಿರುತ್ತದೆ. ಹೀಗಾಗಿ, ಈ ಕೆಳಗಿನ ಪ್ರಮಾಣಪತ್ರಗಳೊಂದಿಗೆ ಫಲಿತಾಂಶವನ್ನು ಪ್ರಮಾಣೀಕರಿಸಬಹುದುಃ ಕೆಂಪು ಮತ್ತು ನೀಲಿ ಲಕೋಟೆಯ ಶೃಂಗಗಳ ಕ್ರಮವನ್ನು ಪ್ರಮಾಣೀಕರಿಸಲು x-ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು () ಬಳಸಲಾಗುತ್ತದೆ. ಅವು ಶೃಂಗಗಳ ಗುಂಪಿನಲ್ಲಿನ ಚಲನಶೀಲ ವಿಂಗಡಿಸಲಾದ ಪಟ್ಟಿಗೆ ಪ್ರಮಾಣಪತ್ರಗಳಾಗಿವೆ. ಪ್ರತಿ ಅಂಕವು 2 ಸಾಲುಗಳನ್ನು ಒಳಗೊಂಡಿರುವುದರಿಂದ ಮತ್ತು ಪ್ರಮಾಣಪತ್ರವು 2 ಅಂಕಗಳನ್ನು ಒಳಗೊಂಡಿರುವುದರಿಂದ, ಪ್ರತಿ ಪ್ರಮಾಣಪತ್ರವು 4 ಸಾಲುಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಒಂದು ಶೃಂಗವು ಅಂಚಿನ ಮೇಲೆ ಅಥವಾ ಕೆಳಗೆ ಇದೆ ಎಂದು ಪ್ರಮಾಣೀಕರಿಸಲು y-ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು () ಬಳಸಲಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಸಮಯದಲ್ಲಿ ಸಂಭವಿಸುವ ಎಲ್ಲಾ ಹೋಲಿಕೆಗಳಿಗೆ ಪ್ರಮಾಣಪತ್ರಗಳು ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತವೆ. ಈ ಎಲ್ಲಾ ಪ್ರಮಾಣಪತ್ರಗಳು ಇರುವವರೆಗೆ, ವಿಲೀನ ಹಂತಗಳನ್ನು ಒಂದೇ ರೀತಿ ಕಾರ್ಯಗತಗೊಳಿಸಲಾಗುತ್ತದೆ, ಆದ್ದರಿಂದ ಪರಿಣಾಮವಾಗಿ ಬರುವ ಮೇಲಿನ ಲಕೋಟೆಯು ಒಂದೇ ಆಗಿರುತ್ತದೆ. ಸ್ಟ್ಯಾಟಿಕ್ ಅಪ್ಪರ್ ಲಕೋಟೆ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಮಾಣೀಕರಿಸಲು ಈ ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು ಬಳಸುವ ಮೂಲಕ ಮೇಲಿನ ಲಕೋಟೆಗಳಿಗೆ ಚಲನಶೀಲ ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ರಚಿಸಬಹುದು. ಆದಾಗ್ಯೂ, ಈ ಯೋಜನೆಯು ಸ್ಥಳೀಯವಾಗಿಲ್ಲ, ಏಕೆಂದರೆ ಒಂದು ಸಾಲು ಇತರ ಲಕೋಟೆಯಿಂದ ಅನೇಕ ಅಂಕಗಳನ್ನು ಎದುರಿಸಿದರೆ ಅದು ಮೇಲ್ಭಾಗದಲ್ಲಿ ಅಥವಾ ಕೆಳಭಾಗದಲ್ಲಿದ್ದರೆ ಅನೇಕ ವೈ-ಪ್ರಮಾಣಪತ್ರಗಳಲ್ಲಿ ತೊಡಗಿಸಿಕೊಳ್ಳುತ್ತದೆ. ಹೀಗಾಗಿ, ಒಂದು ರೇಖೆಯ ಇಳಿಜಾರು ಮತ್ತೊಂದು ರೇಖೆಯ ಇಳಿಜಾರುಗಿಂತ ದೊಡ್ಡದಾಗಿದೆ ಅಥವಾ ಕಡಿಮೆಯಾಗಿದೆ ಎಂದು ಪ್ರಮಾಣೀಕರಿಸುವ s-ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು () ಪರಿಚಯಿಸುವುದು ಅಗತ್ಯವಾಗಿದೆ. ವಿಲೀನದಿಂದ ಉಂಟಾಗುವ ಅಂಚುಗಳು ಮತ್ತು ಶೃಂಗಗಳ ಅನುಕ್ರಮವನ್ನು ಪ್ರಮಾಣೀಕರಿಸಲು ಎಲ್ಲಾ ಬಿಂದುಗಳಿಗೆ ಈ ಕೆಳಗಿನ ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು ಹೊಂದಿರುವುದು ಸಾಕು, ಪ್ರತಿ ಸಾಲಿಗೆ ಕೇವಲ ಒ (1) ಪ್ರಮಾಣಪತ್ರಗಳೊಂದಿಗೆಃ ಅದರ ಬಲಭಾಗಕ್ಕೆ ಹತ್ತಿರವಿರುವ ಶೃಂಗವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಈ ಪ್ರಮಾಣಪತ್ರವನ್ನು ಅವುಗಳನ್ನು ಅನುಸರಿಸುವ ಬಿಂದುವಿಗಿಂತ ವಿಭಿನ್ನ ಬಣ್ಣವನ್ನು ಹೊಂದಿರುವ ಎಲ್ಲಾ ಬಿಂದುಗಳಿಗೆ ಸಂಗ್ರಹಿಸಲಾಗುತ್ತದೆ. : ಅಥವಾ. ಈ ಪ್ರಮಾಣಪತ್ರವನ್ನು ಛೇದಿಸುವ ಎಲ್ಲಾ ಬಿಂದುಗಳಿಗೆ ಸಂಗ್ರಹಿಸಲಾಗುತ್ತದೆ. ಇದು ಸ್ಪರ್ಧಿ ಅಂಚನ್ನು ಸೂಚಿಸುತ್ತದೆ, ಮೇಲಿನ ಅಥವಾ ಕೆಳಗಿರುವ ಇತರ ಲಕೋಟೆಯ ಅಂಚನ್ನು ಸೂಚಿಸುತ್ತದೆ. : ಅಥವಾ. ಈ ಪ್ರಮಾಣಪತ್ರವನ್ನು ಛೇದಿಸುವ ಎಲ್ಲಾ ಬಿಂದುಗಳಿಗೆ ಸಂಗ್ರಹಿಸಲಾಗುತ್ತದೆ. :. ಈ ಪ್ರಮಾಣಪತ್ರವನ್ನು ಎಲ್ಲಾ ಅಂಕಗಳಿಗಾಗಿ ಮತ್ತು ಇದಕ್ಕಾಗಿ ಸಂಗ್ರಹಿಸಲಾಗಿದೆ. :. ಈ ಪ್ರಮಾಣಪತ್ರವನ್ನು ಎಲ್ಲಾ ಅಂಕಗಳಿಗಾಗಿ ಮತ್ತು ಇದಕ್ಕಾಗಿ ಸಂಗ್ರಹಿಸಲಾಗಿದೆ. :. ಈ ಪ್ರಮಾಣಪತ್ರವನ್ನು ಎಲ್ಲಾ ಅಂಕಗಳಿಗಾಗಿ ಮತ್ತು ಇದಕ್ಕಾಗಿ ಸಂಗ್ರಹಿಸಲಾಗಿದೆ. :. ಈ ಪ್ರಮಾಣಪತ್ರವನ್ನು ಎಲ್ಲಾ ಅಂಕಗಳಿಗಾಗಿ ಮತ್ತು ಇದಕ್ಕಾಗಿ ಸಂಗ್ರಹಿಸಲಾಗಿದೆ. :. ಈ ಪ್ರಮಾಣಪತ್ರವನ್ನು ಎಲ್ಲಾ ಅಂಕಗಳಿಗಾಗಿ ಮತ್ತು ಇದಕ್ಕಾಗಿ ಸಂಗ್ರಹಿಸಲಾಗಿದೆ. ಮೊದಲ ಪ್ರಮಾಣಪತ್ರವು, ಕೆಂಪು ಮತ್ತು ನೀಲಿ ಲಕೋಟೆಯಲ್ಲಿನ ಅಂಕಗಳ ಎಕ್ಸ್-ಆರ್ಡರಿಂಗ್ ಅನ್ನು ಪ್ರಮಾಣೀಕರಿಸುತ್ತದೆ. ಎರಡನೇ ಮತ್ತು ಮೂರನೇ ಪ್ರಮಾಣಪತ್ರಗಳು, ಮತ್ತು, ಕೆಂಪು ಮತ್ತು ನೀಲಿ ಲಕೋಟೆಗಳ ಛೇದಕಗಳನ್ನು ಪ್ರಮಾಣೀಕರಿಸುತ್ತವೆ. ಉಳಿದ 5 ಪ್ರಮಾಣಪತ್ರಗಳು,,,, ಮತ್ತು ಮೇಲಿನ ಲಕೋಟೆಯಲ್ಲಿಲ್ಲದ ಅಂಚುಗಳನ್ನು ಅದರ ಮೇಲಿರುವ ಅಂಚುಗಳ ಇಳಿಜಾರುಗಳ ಅನುಕ್ರಮದಲ್ಲಿ ಇರಿಸಿ. ಇಳಿಜಾರು ಅನುಕ್ರಮದ ಪ್ರಾರಂಭ ಅಥವಾ ಅಂತ್ಯದಲ್ಲಿದ್ದರೆ, ಅಥವಾ ಇದನ್ನು ಪ್ರಮಾಣೀಕರಿಸಿ. ಇದು ಅನುಕ್ರಮದ ಮಧ್ಯದಲ್ಲಿದ್ದರೆ, ಮತ್ತು ಇದನ್ನು ಪ್ರಮಾಣೀಕರಿಸಿ, ಮತ್ತು ಅಂಚಿನ ಇಳಿಜಾರು ಇರುವ ಎರಡು ರೇಖೆಗಳ ಛೇದಕ ಬಿಂದುವು ಅದರ ಮೇಲಿದೆ ಎಂದು ಪ್ರಮಾಣೀಕರಿಸುತ್ತದೆ. ಎಲ್ಲಾ ಅಂಚುಗಳು ಈ ರೇಖೆಯ ಮೇಲಿವೆ ಎಂದು ಸಾಬೀತುಪಡಿಸಲು ಈ ಒಂದು ಅಥವಾ ಮೂರು ಪ್ರಮಾಣಪತ್ರಗಳು ಸಾಕಾಗುತ್ತವೆ. ಹಿಂದಿನ ಯೋಜನೆಗಿಂತ ಭಿನ್ನವಾಗಿ, ಎಲ್ಲಾ ಸಾಲುಗಳು ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಪ್ರಮಾಣಪತ್ರಗಳಲ್ಲಿ ಮಾತ್ರ ಒಳಗೊಂಡಿರುತ್ತವೆ. ಈ ಪ್ರಮಾಣಪತ್ರಗಳು ವಿಫಲವಾದಾಗಲೆಲ್ಲಾ, ವಿಲೀನಗೊಂಡ ಲಕೋಟೆಯನ್ನು ಮತ್ತು ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು ಒ (1) ಸಮಯದಲ್ಲಿ ನವೀಕರಿಸಬಹುದು. ಮೇಲ್ಭಾಗದ ಲಕೋಟೆಗಳ ಪುನರಾವರ್ತಿತ ವಿಲೀನವನ್ನು ಪ್ರಮಾಣೀಕರಿಸಲು ಈ ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು ಬಳಸುವ ಮೂಲಕ ಕನ್ವೆಕ್ಸ್ ಹಲ್ಗಾಗಿ ಕೈನೆಟಿಕ್ ಡೇಟಾ ರಚನೆಯನ್ನು ನಿರ್ಮಿಸಲಾಗಿದೆ. ಪ್ರಮಾಣಪತ್ರಗಳು ವಿಫಲವಾದಾಗಲೆಲ್ಲಾ, ಅವುಗಳ ವಿಲೀನವನ್ನು ನವೀಕರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ವಿಲೀನದಿಂದ ಉಂಟಾಗುವ ಲಕೋಟೆಯು ಬದಲಾದರೆ, ವಿಲೀನದ ಫಲಿತಾಂಶವನ್ನು ಅವಲಂಬಿಸಿರುವ ಎಲ್ಲಾ ವಿಲೀನಗಳ ಮೂಲಕ ಬದಲಾವಣೆಗಳನ್ನು ಪ್ರಚಾರ ಮಾಡಲಾಗುತ್ತದೆ. ಕಾರ್ಯಕ್ಷಮತೆ ಈ ದತ್ತಾಂಶ ರಚನೆಯು ಸ್ಪಂದಿಸುವ, ಸ್ಥಳೀಯ, ಸಾಂದ್ರ ಮತ್ತು ಪರಿಣಾಮಕಾರಿಯಾಗಿದೆ. ಮೇಲಿನ ಲಕೋಟೆಯನ್ನು ಪ್ರಮಾಣೀಕರಿಸಲು ಬಳಸುವ ವಿಲೀನಗಳ ಲಾಗರಿಥಮಿಕ್ ಆಳ ಇದಕ್ಕೆ ಕಾರಣ. ಪ್ರತಿಕ್ರಿಯಾತ್ಮಕಃ ಪ್ರಮಾಣಪತ್ರವು ವಿಫಲವಾದಾಗ, ಅದು ಪ್ರಮಾಣೀಕರಿಸುವ ವಿಲೀನವನ್ನು ಸರಿಪಡಿಸಲು ಒ (1) ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಪರಿಣಾಮವಾಗಿ ಬರುವ ಲಕೋಟೆಯು ಬದಲಾದರೆ, ಬದಲಾದ ವಿಲೀನದ ಫಲಿತಾಂಶವನ್ನು ಅವಲಂಬಿಸಿರುವ ಎಲ್ಲಾ ವಿಲೀನಗಳವರೆಗೆ ಬದಲಾವಣೆಯನ್ನು ಪ್ರಚಾರ ಮಾಡಬೇಕು. ಅಂತಹ ಒ (ಲಾಗ್ ಎನ್) ವಿಲೀನಗಳಿವೆ, ಆದ್ದರಿಂದ ನವೀಕರಣವನ್ನು ಒಟ್ಟು ಒ (ಲಾಗ್ ಎನ್) ಸಮಯದಲ್ಲಿ ಮಾಡಬಹುದು. ಸ್ಥಳೀಯಃ ಪ್ರತಿ ಸಾಲು ಹೆಚ್ಚಿನ ಒ (ಲಾಗ್ ಎನ್) ಪ್ರಮಾಣಪತ್ರಗಳಲ್ಲಿ ಒಳಗೊಂಡಿರುತ್ತದೆ. ಏಕೆಂದರೆ ಪ್ರತಿ ಸಾಲು ಪ್ರತಿ ವಿಲೀನದಲ್ಲಿ ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಸಾಲು ಒ (ಲಾಗ್ ಎನ್) ಒಟ್ಟು ವಿಲೀನಗಳಲ್ಲಿ ಇರುತ್ತದೆ. ಸಾಂದ್ರತೆಃ ಈ ದತ್ತಾಂಶ ರಚನೆಯಲ್ಲಿ ಬಳಸಲಾಗುವ ಪ್ರಮಾಣಪತ್ರಗಳ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯು ಒ (ಎನ್ ಲಾಗ್ ಎನ್) ಆಗಿದೆ. ಏಕೆಂದರೆ ಪ್ರತಿ ವಿಲೀನವು ವಿಲೀನಗೊಂಡ ರೇಖೆಗಳ ಸಂಖ್ಯೆಗೆ ರೇಖೀಯವಾದ ಹಲವಾರು ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. n ಸಾಲುಗಳ ಮೇಲಿನ ಲಕೋಟೆಯನ್ನು ಪ್ರಮಾಣೀಕರಿಸಲು n/2 ಸಾಲುಗಳ ಎರಡು ಉಪಗುಂಪುಗಳ ಮೇಲಿನ ಲಕೋಟೆಯ ವಿಲೀನಕ್ಕೆ ಪ್ರಮಾಣಪತ್ರಗಳು ಮತ್ತು ಲಕೋಟೆಗಳ ವಿಲೀನಕ್ಕೆ ಪ್ರಮಾಣಪತ್ರಗಳು ಬೇಕಾಗುತ್ತವೆ. ಹೀಗಾಗಿ n ಸಾಲುಗಳ ಮೇಲಿನ ಲಕೋಟೆಯನ್ನು ಪ್ರಮಾಣೀಕರಿಸಲು ಅಗತ್ಯವಾದ ಪ್ರಮಾಣಪತ್ರಗಳ ಸಂಖ್ಯೆ, C (n), C (1) = O (1) ನೊಂದಿಗೆ ಪುನರಾವರ್ತನೆ C (n) = 2C (n/2) + O (n) ಅನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ. ವಿಭಜನೆ-ಮತ್ತು-ವಶಪಡಿಸಿಕೊಳ್ಳುವ ಪುನರಾವರ್ತನೆಗಳ ಮುಖ್ಯ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, C (n) = O (n log n). ದಕ್ಷತೆಃ ಬೀಜಗಣಿತದ ಅಥವಾ ಹುಸಿ-ಬೀಜಗಣಿತದ ಪಥಗಳ ಮೇಲೆ ಈ ಕ್ರಮಾವಳಿಯಿಂದ ಸಂಸ್ಕರಿಸಲಾದ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಘಟನೆಗಳು ಎಲ್ಲರಿಗೂ ಚತುರ್ಭುಜಕ್ಕೆ ಹತ್ತಿರದಲ್ಲಿವೆ. ರೇಖೀಯವಾಗಿ ಚಲಿಸುವ ಬಿಂದುಗಳ ಕನ್ವೆಕ್ಸ್ ಹಲ್ಗಳು ಸಮಯವನ್ನು ಬದಲಾಯಿಸಬಹುದು. ಹೀಗಾಗಿ ಈ ದತ್ತಾಂಶ ರಚನೆಯು ಪರಿಣಾಮಕಾರಿಯಾಗಿದೆ. ಹೆಚ್ಚಿನ ಆಯಾಮಗಳು 2 ಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಆಯಾಮಗಳಲ್ಲಿ ಚಲಿಸುವ ಬಿಂದುಗಳ ಕನ್ವೆಕ್ಸ್ ಹಲ್ ಅನ್ನು ನಿರ್ವಹಿಸಲು ಪರಿಣಾಮಕಾರಿ ಚಲನೆಯ ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಒಂದು ಮುಕ್ತ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಸಂಬಂಧಿತ ಸಮಸ್ಯೆಗಳು ಈ ಕೆಳಗಿನ ಸಂಬಂಧಿತ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಕೈನೆಟಿಕ್ ಕನ್ವೆಕ್ಸ್ ಹಲ್ ಅನ್ನು ಬಳಸಬಹುದುಃ ಕೈನೆಟಿಕ್ ವ್ಯಾಸ ಕೈನೆಟಿಕ್ ಅಗಲ ಕೈನೆಟಿಕ್ ಕನಿಷ್ಠ ಪೆಟ್ಟಿಗೆ ಕೈನೆಟಿಕ್ ಚಿಕ್ಕ ಸುತ್ತುವ ಡಿಸ್ಕ್ ಉಲ್ಲೇಖಗಳು ಕೈನೆಟಿಕ್ ದತ್ತಾಂಶ ರಚನೆಗಳು ಕನ್ವೆಕ್ಸ್ ಹಲ್ ಕ್ರಮಾವಳಿಗಳು