Unlocking Faster Typing: A Geometric Approach to Keyboard Design

The QWERTY keyboard, a staple of our digital lives, was designed to solve a problem that no longer exists: preventing typewriter jams. But in today's digital world, is it truly the most efficient layout? Researchers Jules Deschamps, Quentin Hubert, and Lucas Ryckelynck, in their COMSW4995 002 project, tackled this question head-on, using geometric analysis to design faster-typing keyboards.

To optimize keyboard design, the team first needed to understand how we use the English language. They analyzed the frequency of individual letters and the probabilities of letter transitions (like 'th' or 'er'). This data was then used to create a Markov Chain model, essentially a mathematical representation of how letters follow each other. The transition probabilities are shown in Image 1, and Image 2 shows the frequency of each letter.

The team explored a 'geometric non-layout' approach. They treated letters as points in space and aimed to minimize the distance your hands travel while typing. This approach led to two distinct keyboard models: one-handed (H1) and two-handed (H2). The goal was to find the optimal arrangement of these letter-points to reduce typing time.

For the H1 keyboard, the researchers used an optimization process to determine the distances between letters, then employed Multi-Dimensional Scaling (MDS) to visualize these distances in 2D space. The resulting layout, shown in Image 3, places frequently used letters in the center and less common letters further out. This provides the foundation for the one-handed keyboard.

The H2 keyboard considered the more common two-handed typing style. This involved clustering letters into two groups (left and right hands). The team then optimized the layout within each cluster. Images 4 and 5 show the 2D embedding of the first and second clusters, respectively.

To understand the 'shape' of these keyboards, the researchers analyzed their curvature using discrete Ricci curvature. This analysis revealed how letters connect and how frequently they are used together. Letters with high curvature, like 'z', are less frequently used, while letters with low curvature, like 'o', are more common. The curvature analysis for the H1 keyboard is shown in Image 6, and for the H2 keyboard, the curvature is shown in Images 7 and 8.

The researchers then used integer programming (IP) to directly design keyboard layouts. They aimed to minimize the distance your fingers travel based on the letter transition frequencies. While a direct IP approach proved too complex, they leveraged the 2D embeddings from the geometric analysis. Image 9, 10, 11, and 12 shows examples of the resulting keyboard layouts.

To validate their designs, the team created a testing framework. They compared the performance of their H1 and H2 keyboards against the standard QWERTY layout. The results, visualized in Images 13, 14, and 15, showed that the H1 keyboard improved typing efficiency by 20%, while the H2 keyboard saw a smaller, but still significant, 2.8% improvement. The covariance ellipse results (Images 16 and 17) confirm the model's efficiency by showing the dispersion of the hands across the keyboard.

The study also explores avenues for future research. One key area is designing keyboards optimized for multiple languages. By analyzing the letter frequencies and transition probabilities across different languages, the team aims to create a keyboard that adapts to various linguistic patterns.

This research provides a fascinating look into the intersection of geometry, language, and keyboard design. The team's work demonstrates how mathematical modeling can lead to real-world improvements in everyday technology. The H1 keyboard is 20% faster than QWERTY-1, and the H2 keyboard is 3% faster than QWERTY-2. While there's still room for improvement, the study lays a solid foundation for future innovations in keyboard layout optimization.