diff --git a/java/res/values-land/dimens.xml b/java/res/values-land/dimens.xml
index 043f4b3..15f356d 100644
--- a/java/res/values-land/dimens.xml
+++ b/java/res/values-land/dimens.xml
@@ -28,8 +28,8 @@
     <dimen name="candidate_strip_fading_edge_length">63dip</dimen>
     <dimen name="spacebar_vertical_correction">2dip</dimen>
     <!-- Amount of allowance for selecting keys in a mini popup keyboard by sliding finger. -->
-    <!-- popup_key_height x 1.7 -->
-    <dimen name="mini_keyboard_slide_allowance">0.459in</dimen>
+    <!-- popup_key_height x 1.2 -->
+    <dimen name="mini_keyboard_slide_allowance">0.324in</dimen>
     <!-- popup_key_height x 1.0 -->
     <dimen name="mini_keyboard_vertical_correction">-0.270in</dimen>
 </resources>
diff --git a/java/res/values-xlarge/dimens.xml b/java/res/values-xlarge/dimens.xml
index a60d604..72110ca 100644
--- a/java/res/values-xlarge/dimens.xml
+++ b/java/res/values-xlarge/dimens.xml
@@ -28,8 +28,8 @@
     <!-- key_height x 1.6 -->
     <dimen name="key_preview_height">0.720in</dimen>
     <!-- Amount of allowance for selecting keys in a mini popup keyboard by sliding finger. -->
-    <!-- popup_key_height x 1.7 -->
-    <dimen name="mini_keyboard_slide_allowance">0.765in</dimen>
+    <!-- popup_key_height x 1.2 -->
+    <dimen name="mini_keyboard_slide_allowance">0.540in</dimen>
     <!-- popup_key_height x 1.0 -->
     <dimen name="mini_keyboard_vertical_correction">-0.450in</dimen>
 
diff --git a/java/res/values/dimens.xml b/java/res/values/dimens.xml
index a2ce364..5267f3b 100644
--- a/java/res/values/dimens.xml
+++ b/java/res/values/dimens.xml
@@ -28,8 +28,8 @@
     <!-- key_preview_text_size_large x 2 -->
     <dimen name="key_preview_height">80sp</dimen>
     <!-- Amount of allowance for selecting keys in a mini popup keyboard by sliding finger. -->
-    <!-- popup_key_height x 1.7 -->
-    <dimen name="mini_keyboard_slide_allowance">0.553in</dimen>
+    <!-- popup_key_height x 1.2 -->
+    <dimen name="mini_keyboard_slide_allowance">0.390in</dimen>
     <!-- popup_key_height x 1.0 -->
     <dimen name="mini_keyboard_vertical_correction">-0.325in</dimen>
 
diff --git a/java/src/com/android/inputmethod/latin/BaseKeyboard.java b/java/src/com/android/inputmethod/latin/BaseKeyboard.java
index 266300e..e5b2756 100644
--- a/java/src/com/android/inputmethod/latin/BaseKeyboard.java
+++ b/java/src/com/android/inputmethod/latin/BaseKeyboard.java
@@ -24,7 +24,6 @@
 import android.content.res.XmlResourceParser;
 import android.graphics.drawable.Drawable;
 import android.text.TextUtils;
-import android.util.DisplayMetrics;
 import android.util.Log;
 import android.util.TypedValue;
 import android.util.Xml;
@@ -109,15 +108,16 @@
 
     // Variables for pre-computing nearest keys.
 
-    private final int GRID_WIDTH;
-    private final int GRID_HEIGHT;
+    public final int GRID_WIDTH;
+    public final int GRID_HEIGHT;
     private final int GRID_SIZE;
     private int mCellWidth;
     private int mCellHeight;
     private int[][] mGridNeighbors;
     private int mProximityThreshold;
+    private static int[] EMPTY_INT_ARRAY = new int[0];
     /** Number of key widths from current touch point to search for nearest keys. */
-    private static float SEARCH_DISTANCE = 1.8f;
+    private static float SEARCH_DISTANCE = 1.2f;
 
     /**
      * Container for keys in the keyboard. All keys in a row are at the same Y-coordinate.
@@ -402,18 +402,21 @@
         }
 
         /**
-         * Returns the square of the distance between the center of the key and the given point.
+         * Returns the square of the distance to the nearest edge of the key and the given point.
          * @param x the x-coordinate of the point
          * @param y the y-coordinate of the point
-         * @return the square of the distance of the point from the center of the key
+         * @return the square of the distance of the point from the nearest edge of the key
          */
-        public int squaredDistanceFrom(int x, int y) {
-            // We should count vertical gap between rows to calculate the center of this Key.
-            // TODO: We should re-think how we define the center of the key.
-            final int verticalGap = keyboard.getVerticalGap();
-            int xDist = this.x + width / 2 - x;
-            int yDist = this.y + (height + verticalGap) / 2 - y;
-            return xDist * xDist + yDist * yDist;
+        public int squaredDistanceToEdge(int x, int y) {
+            final int left = this.x;
+            final int right = left + this.width;
+            final int top = this.y;
+            final int bottom = top + this.height;
+            final int edgeX = x < left ? left : (x > right ? right : x);
+            final int edgeY = y < top ? top : (y > bottom ? bottom : y);
+            final int dx = x - edgeX;
+            final int dy = y - edgeY;
+            return dx * dx + dy * dy;
         }
 
         /**
@@ -633,24 +636,21 @@
         mCellWidth = (getMinWidth() + GRID_WIDTH - 1) / GRID_WIDTH;
         mCellHeight = (getHeight() + GRID_HEIGHT - 1) / GRID_HEIGHT;
         mGridNeighbors = new int[GRID_SIZE][];
-        int[] indices = new int[mKeys.size()];
+        final int[] indices = new int[mKeys.size()];
         final int gridWidth = GRID_WIDTH * mCellWidth;
         final int gridHeight = GRID_HEIGHT * mCellHeight;
+        final int threshold = mProximityThreshold;
         for (int x = 0; x < gridWidth; x += mCellWidth) {
             for (int y = 0; y < gridHeight; y += mCellHeight) {
+                final int centerX = x + mCellWidth / 2;
+                final int centerY = y + mCellHeight / 2;
                 int count = 0;
                 for (int i = 0; i < mKeys.size(); i++) {
                     final Key key = mKeys.get(i);
-                    final int threshold = mProximityThreshold;
-                    if (key.squaredDistanceFrom(x, y) < threshold ||
-                            key.squaredDistanceFrom(x + mCellWidth - 1, y) < threshold ||
-                            key.squaredDistanceFrom(x + mCellWidth - 1, y + mCellHeight - 1)
-                                < threshold ||
-                            key.squaredDistanceFrom(x, y + mCellHeight - 1) < threshold) {
+                    if (key.squaredDistanceToEdge(centerX, centerY) < threshold)
                         indices[count++] = i;
-                    }
                 }
-                int [] cell = new int[count];
+                final int[] cell = new int[count];
                 System.arraycopy(indices, 0, cell, 0, count);
                 mGridNeighbors[(y / mCellHeight) * GRID_WIDTH + (x / mCellWidth)] = cell;
             }
@@ -672,7 +672,7 @@
                 return mGridNeighbors[index];
             }
         }
-        return new int[0];
+        return EMPTY_INT_ARRAY;
     }
 
     // TODO should be private
diff --git a/java/src/com/android/inputmethod/latin/BaseKeyboardView.java b/java/src/com/android/inputmethod/latin/BaseKeyboardView.java
index 4ba6fbd..070d031 100644
--- a/java/src/com/android/inputmethod/latin/BaseKeyboardView.java
+++ b/java/src/com/android/inputmethod/latin/BaseKeyboardView.java
@@ -71,6 +71,7 @@
 public class BaseKeyboardView extends View implements PointerTracker.UIProxy {
     private static final String TAG = "BaseKeyboardView";
     private static final boolean DEBUG = false;
+    private static final boolean DEBUG_KEYBOARD_GRID = false;
 
     public static final int NOT_A_TOUCH_COORDINATE = -1;
 
@@ -183,8 +184,6 @@
     // Main keyboard
     private BaseKeyboard mKeyboard;
     private Key[] mKeys;
-    // TODO this attribute should be gotten from Keyboard.
-    private int mKeyboardVerticalGap;
 
     // Key preview popup
     private boolean mInForeground;
@@ -609,7 +608,6 @@
         LatinImeLogger.onSetKeyboard(keyboard);
         mKeys = mKeyDetector.setKeyboard(keyboard, -getPaddingLeft(),
                 -getPaddingTop() + mVerticalCorrection);
-        mKeyboardVerticalGap = (int)getResources().getDimension(R.dimen.key_bottom_gap);
         for (PointerTracker tracker : mPointerTrackers) {
             tracker.setKeyboard(keyboard, mKeys, mKeyHysteresisDistance);
         }
@@ -617,7 +615,7 @@
         // Hint to reallocate the buffer if the size changed
         mKeyboardChanged = true;
         invalidateAllKeys();
-        computeProximityThreshold(keyboard);
+        computeProximityThreshold(keyboard, mKeys);
         mMiniKeyboardCache.clear();
     }
 
@@ -713,23 +711,27 @@
     }
 
     /**
-     * Compute the average distance between adjacent keys (horizontally and vertically)
-     * and square it to get the proximity threshold. We use a square here and in computing
-     * the touch distance from a key's center to avoid taking a square root.
+     * Compute the most common key width and use it as proximity key detection threshold.
      * @param keyboard
+     * @param keys
      */
-    private void computeProximityThreshold(BaseKeyboard keyboard) {
-        if (keyboard == null) return;
-        final Key[] keys = mKeys;
-        if (keys == null) return;
-        int length = keys.length;
-        int dimensionSum = 0;
-        for (int i = 0; i < length; i++) {
-            Key key = keys[i];
-            dimensionSum += Math.min(key.width, key.height + mKeyboardVerticalGap) + key.gap;
+    private void computeProximityThreshold(BaseKeyboard keyboard, Key[] keys) {
+        if (keyboard == null || keys == null || keys.length == 0) return;
+        final HashMap<Integer, Integer> histogram = new HashMap<Integer, Integer>();
+        int maxCount = 0;
+        int mostCommonWidth = 0;
+        for (Key key : keys) {
+            final Integer width = key.width + key.gap;
+            Integer count = histogram.get(width);
+            if (count == null)
+                count = 0;
+            histogram.put(width, ++count);
+            if (count > maxCount) {
+                maxCount = count;
+                mostCommonWidth = width;
+            }
         }
-        if (dimensionSum < 0 || length == 0) return;
-        mKeyDetector.setProximityThreshold((int) (dimensionSum * 1.4f / length));
+        mKeyDetector.setProximityThreshold(mostCommonWidth);
     }
 
     @Override
@@ -868,6 +870,20 @@
             }
             canvas.translate(-key.x - kbdPaddingLeft, -key.y - kbdPaddingTop);
         }
+
+        if (DEBUG_KEYBOARD_GRID) {
+            Paint p = new Paint();
+            p.setStyle(Paint.Style.STROKE);
+            p.setStrokeWidth(1.0f);
+            p.setColor(0x800000c0);
+            int cw = (mKeyboard.getMinWidth() + mKeyboard.GRID_WIDTH - 1) / mKeyboard.GRID_WIDTH;
+            int ch = (mKeyboard.getHeight() + mKeyboard.GRID_HEIGHT - 1) / mKeyboard.GRID_HEIGHT;
+            for (int i = 0; i <= mKeyboard.GRID_WIDTH; i++)
+                canvas.drawLine(i * cw, 0, i * cw, ch * mKeyboard.GRID_HEIGHT, p);
+            for (int i = 0; i <= mKeyboard.GRID_HEIGHT; i++)
+                canvas.drawLine(0, i * ch, cw * mKeyboard.GRID_WIDTH, i * ch, p);
+        }
+
         mInvalidatedKey = null;
         // Overlay a dark rectangle to dim the keyboard
         if (mMiniKeyboard != null) {
diff --git a/java/src/com/android/inputmethod/latin/MiniKeyboardKeyDetector.java b/java/src/com/android/inputmethod/latin/MiniKeyboardKeyDetector.java
index 0e0c2e7..3cc43b9 100644
--- a/java/src/com/android/inputmethod/latin/MiniKeyboardKeyDetector.java
+++ b/java/src/com/android/inputmethod/latin/MiniKeyboardKeyDetector.java
@@ -41,17 +41,18 @@
         final Key[] keys = getKeys();
         final int touchX = getTouchX(x);
         final int touchY = getTouchY(y);
+
         int closestKeyIndex = BaseKeyboardView.NOT_A_KEY;
         int closestKeyDist = (y < 0) ? mSlideAllowanceSquareTop : mSlideAllowanceSquare;
         final int keyCount = keys.length;
-        for (int i = 0; i < keyCount; i++) {
-            final Key key = keys[i];
-            int dist = key.squaredDistanceFrom(touchX, touchY);
+        for (int index = 0; index < keyCount; index++) {
+            final int dist = keys[index].squaredDistanceToEdge(touchX, touchY);
             if (dist < closestKeyDist) {
-                closestKeyIndex = i;
+                closestKeyIndex = index;
                 closestKeyDist = dist;
             }
         }
+
         if (allKeys != null && closestKeyIndex != BaseKeyboardView.NOT_A_KEY)
             allKeys[0] = keys[closestKeyIndex].codes[0];
         return closestKeyIndex;
diff --git a/java/src/com/android/inputmethod/latin/PointerTracker.java b/java/src/com/android/inputmethod/latin/PointerTracker.java
index 78e0072..2194ed9 100644
--- a/java/src/com/android/inputmethod/latin/PointerTracker.java
+++ b/java/src/com/android/inputmethod/latin/PointerTracker.java
@@ -396,24 +396,12 @@
         if (newKey == curKey) {
             return true;
         } else if (isValidKeyIndex(curKey)) {
-            return getSquareDistanceToKeyEdge(x, y, mKeys[curKey]) < mKeyHysteresisDistanceSquared;
+            return mKeys[curKey].squaredDistanceToEdge(x, y) < mKeyHysteresisDistanceSquared;
         } else {
             return false;
         }
     }
 
-    private static int getSquareDistanceToKeyEdge(int x, int y, Key key) {
-        final int left = key.x;
-        final int right = key.x + key.width;
-        final int top = key.y;
-        final int bottom = key.y + key.height;
-        final int edgeX = x < left ? left : (x > right ? right : x);
-        final int edgeY = y < top ? top : (y > bottom ? bottom : y);
-        final int dx = x - edgeX;
-        final int dy = y - edgeY;
-        return dx * dx + dy * dy;
-    }
-
     private void showKeyPreviewAndUpdateKeyGraphics(int keyIndex) {
         updateKeyGraphics(keyIndex);
         // The modifier key, such as shift key, should not be shown as preview when multi-touch is
diff --git a/java/src/com/android/inputmethod/latin/ProximityKeyDetector.java b/java/src/com/android/inputmethod/latin/ProximityKeyDetector.java
index 01122eb..35bdc67 100644
--- a/java/src/com/android/inputmethod/latin/ProximityKeyDetector.java
+++ b/java/src/com/android/inputmethod/latin/ProximityKeyDetector.java
@@ -36,41 +36,34 @@
         final Key[] keys = getKeys();
         final int touchX = getTouchX(x);
         final int touchY = getTouchY(y);
-        int primaryIndex = BaseKeyboardView.NOT_A_KEY;
-        int closestKey = BaseKeyboardView.NOT_A_KEY;
-        int closestKeyDist = mProximityThresholdSquare + 1;
-        int[] distances = mDistances;
-        Arrays.fill(distances, Integer.MAX_VALUE);
-        int [] nearestKeyIndices = mKeyboard.getNearestKeys(touchX, touchY);
-        final int keyCount = nearestKeyIndices.length;
-        for (int i = 0; i < keyCount; i++) {
-            final Key key = keys[nearestKeyIndices[i]];
-            int dist = 0;
-            boolean isInside = key.isInside(touchX, touchY);
-            if (isInside) {
-                primaryIndex = nearestKeyIndices[i];
-            }
 
-            if (((mProximityCorrectOn
-                    && (dist = key.squaredDistanceFrom(touchX, touchY)) < mProximityThresholdSquare)
-                    || isInside)
-                    && key.codes[0] > 32) {
-                // Find insertion point
-                final int nCodes = key.codes.length;
+        int primaryIndex = BaseKeyboardView.NOT_A_KEY;
+        int closestKeyIndex = BaseKeyboardView.NOT_A_KEY;
+        int closestKeyDist = mProximityThresholdSquare + 1;
+        final int[] distances = mDistances;
+        Arrays.fill(distances, Integer.MAX_VALUE);
+        for (final int index : mKeyboard.getNearestKeys(touchX, touchY)) {
+            final Key key = keys[index];
+            final boolean isInside = key.isInside(touchX, touchY);
+            if (isInside)
+                primaryIndex = index;
+            final int dist = key.squaredDistanceToEdge(touchX, touchY);
+            if (isInside || (mProximityCorrectOn && dist < mProximityThresholdSquare)) {
                 if (dist < closestKeyDist) {
                     closestKeyDist = dist;
-                    closestKey = nearestKeyIndices[i];
+                    closestKeyIndex = index;
                 }
 
                 if (allKeys == null) continue;
-
+                final int nCodes = key.codes.length;
+                // Find insertion point
                 for (int j = 0; j < distances.length; j++) {
                     if (distances[j] > dist) {
                         // Make space for nCodes codes
                         System.arraycopy(distances, j, distances, j + nCodes,
-                                distances.length - j - nCodes);
+                                distances.length - (j + nCodes));
                         System.arraycopy(allKeys, j, allKeys, j + nCodes,
-                                allKeys.length - j - nCodes);
+                                allKeys.length - (j + nCodes));
                         System.arraycopy(key.codes, 0, allKeys, j, nCodes);
                         Arrays.fill(distances, j, j + nCodes, dist);
                         break;
@@ -78,9 +71,7 @@
                 }
             }
         }
-        if (primaryIndex == BaseKeyboardView.NOT_A_KEY) {
-            primaryIndex = closestKey;
-        }
-        return primaryIndex;
+
+        return primaryIndex == BaseKeyboardView.NOT_A_KEY ? closestKeyIndex : primaryIndex;
     }
 }