Efficient Algorithms for the Four Corners Problem and Two-Dimensional Pattern Matching

Ari Liloia and Michael Wehar, Department of Computer Science, Swarthmore College, 500 College Avenue, Swarthmore PA 19081

Two dimensional pattern matching is concerned with the recognition of patterns within two dimensional data structures, such as binary matrices, which are matrices whose elements have one of two possible values. There are many algorithmic problems related to efficiently recognizing patterns within binary matrices. One such problem asks: Given a rectangular matrix made up of ones and zeros, does there exist a submatrix whose four corners are all ones? This problem is referred to as the Four Corners Problem. It appears on many algorithms challenge websites and it has applications to the well known frequent itemsets problem from data mining. The standard solution for the Four Corners Problem runs in cubic time.  Through an ongoing research project with my advisor (and several collaborators) we were able to improve the standard solution by designing and implementing a more efficient algorithm.  In particular, we were able to introduce nearly quadratic time algorithms for all common variations of the Four Corners Problem over a binary alphabet, each of which involves one of the four possible configurations of corner values (1111, 1011, 1001, or 1010).  We then implemented our algorithms in Python and made our code available in an open source repository on GitHub, so that other researchers can use these algorithms to solve new problems.  Our code was written following principles of software design that advocate for simplicity and readability, making it ideal for usage in a classroom setting for educational purposes.  In addition, we showed that the Four Corners Problem is equivalent to several problems related to data mining and computational geometry, offering applications of our work to other problems within computer science, including frequent itemset mining, the buyer-seller matching problem, and finding rectangles in sets of points.

Additional Abstract Information

Presenter: Ari Liloia

Institution: Swarthmore College

Type: Poster

Subject: Computer Science

Status: Approved

Time and Location

Session: Poster 5
Date/Time: Tue 12:30pm-1:30pm
Session Number: 4042