가시적 격자점 문제를 이용한 안드로이드 잠금 패턴 가짓수의 상계와 하계 범위 개선

Improving the Upper and Lower Bounds for Android Locking Patterns using Visible Grid Point Problem

격자 평면 위 임의의 점에서 다른 점을 볼 수 있는 비율은 6/π²이라는 가시적 격자점 문제는 무한 격자 평면에 기반을 둔 것이다. 하지만 5×5 이상 의유한 격자 평면에서는 경우의 수(전체탐색법)만으로 그 가짓수를 모두 구하는 것은 어렵다. 본 연구는 선행연구들을 바탕으로 유한 격자 평면으로 국한할 때의 안드로이드 잠금 패턴의 가짓수 범위(상계와 하계)를 구하는 알고리즘을 개발하였다. 특히 좌표평면 위 점의 위치에 따른 가시적 격자점 비율의 상계와 하계를 미지수화하여 경우의 수에 따라 세분화하면서 공식화하였다. 이 공식을 바탕으로 Python Coding으로는 오버플로가 발생하지 않는 범위(13×13 격자판) 내에서 일부의 하계 값과 대부분의 상계 값을 개선시켰다. 이 연구는 Lee(2017)가 제시하였던 가시성에 기반하지 않은 연구에서의 알고리즘을 발전시켰고 최승훈 (2017)이 제안한 가시성에 기반한 연구와 Goodrich, et, al. (2018)과는 Visible Grid Point Problem에 공통점이 있다. 그러나 이들의 연구 결과 값을 일부 개선했던 정성재, 김현호, 송상헌(2018)과도 상계와 하계를 구하려는 목적은 같으나 이를 구하는 과정과 방법에 차이가 있다.

In larger than 5×5 grid, the number of Android locking pattern to solve using full search is hard. In this study, the Visible Grid point Problem is applied to obtain a possible number of patterns. This problem will be expanded. In original, Visible Grid Point Problem have been studied with infinite grid, while in this study, it extends to finite grid. With reference to the process of solving ratio of visible points of arbitrary point in infinite grid, 6/π², we solved the ratio of visible points to arbitrary point in the finite plane. However, it is difficult to obtain the accurate ratio of visible points to arbitrary point in the finite plane. Thus, by calculating the upper bound and lower bound of this ratio, we obtained the upper bound and lower bound of the numbers of the Android locking patterns’ possible parameters to see the approximate range of the possible parameters. So, all of upper bounds are improved.