We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
ensure_spacing function may be slow
## Description

The `skimage._shared.coord.ensure_spacing` function introduced in #4760 may be slow when the number of input points is large.

## Way to reproduce
```python
In [1]: import numpy as np

In [2]: from skimage._shared.coord import ensure_spacing

In [3]: for n in range(500, 10001, 500):
    ...:     print(f"n = {n}")
    ...:     x = np.random.rand(n, 2)
    ...:     %timeit ensure_spacing(x, 0.2)
    ...: 
n = 500
27.6 ms ± 857 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
n = 1000
64.7 ms ± 1.93 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
n = 1500
105 ms ± 2.27 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
n = 2000
158 ms ± 1.18 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
n = 2500
213 ms ± 7.32 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 3000
299 ms ± 11.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 3500
378 ms ± 3.05 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 4000
428 ms ± 11.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 4500
554 ms ± 14 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 5000
647 ms ± 9.42 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 5500
777 ms ± 7.05 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 6000
870 ms ± 13.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 6500
1.03 s ± 9.56 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 7000
1.17 s ± 12.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 7500
1.33 s ± 28 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 8000
1.45 s ± 18.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 8500
1.63 s ± 36.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 9000
1.87 s ± 50.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 9500
2.07 s ± 23.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
n = 10000
2.29 s ± 51.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `skimage/_shared/coord.py`
Content:
```
1 import numpy as np
2 from scipy.spatial import cKDTree, distance
3 
4 
5 def ensure_spacing(coord, spacing=1, p_norm=np.inf):
6     """Returns a subset of coord where a minimum spacing is guaranteed.
7 
8     Parameters
9     ----------
10     coord : ndarray
11         The coordinates of the considered points.
12     spacing : float
13         the maximum allowed spacing between the points.
14     p_norm : float
15         Which Minkowski p-norm to use. Should be in the range [1, inf].
16         A finite large p may cause a ValueError if overflow can occur.
17         ``inf`` corresponds to the Chebyshev distance and 2 to the
18         Euclidean distance.
19 
20     Returns
21     -------
22     output : ndarray
23         A subset of coord where a minimum spacing is guaranteed.
24 
25     """
26 
27     output = coord
28     if len(coord):
29         # Use KDtree to find the peaks that are too close to each other
30         tree = cKDTree(coord)
31 
32         indices = tree.query_ball_point(coord, r=spacing, p=p_norm)
33         rejected_peaks_indices = set()
34         for idx, candidates in enumerate(indices):
35             if idx not in rejected_peaks_indices:
36                 # keep current point and the points at exactly spacing from it
37                 candidates.remove(idx)
38                 dist = distance.cdist([coord[idx]],
39                                       coord[candidates],
40                                       distance.minkowski,
41                                       p=p_norm).reshape(-1)
42                 candidates = [c for c, d in zip(candidates, dist)
43                               if d < spacing]
44 
45                 # candidates.remove(keep)
46                 rejected_peaks_indices.update(candidates)
47 
48         # Remove the peaks that are too close to each other
49         output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)
50 
51     return output
52
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/skimage/_shared/coord.py b/skimage/_shared/coord.py
--- a/skimage/_shared/coord.py
+++ b/skimage/_shared/coord.py
@@ -2,7 +2,7 @@
 from scipy.spatial import cKDTree, distance
 
 
-def ensure_spacing(coord, spacing=1, p_norm=np.inf):
+def _ensure_spacing(coord, spacing, p_norm):
     """Returns a subset of coord where a minimum spacing is guaranteed.
 
     Parameters
@@ -24,28 +24,72 @@
 
     """
 
-    output = coord
-    if len(coord):
-        # Use KDtree to find the peaks that are too close to each other
-        tree = cKDTree(coord)
-
-        indices = tree.query_ball_point(coord, r=spacing, p=p_norm)
-        rejected_peaks_indices = set()
-        for idx, candidates in enumerate(indices):
-            if idx not in rejected_peaks_indices:
-                # keep current point and the points at exactly spacing from it
-                candidates.remove(idx)
-                dist = distance.cdist([coord[idx]],
-                                      coord[candidates],
-                                      distance.minkowski,
-                                      p=p_norm).reshape(-1)
-                candidates = [c for c, d in zip(candidates, dist)
-                              if d < spacing]
-
-                # candidates.remove(keep)
-                rejected_peaks_indices.update(candidates)
-
-        # Remove the peaks that are too close to each other
-        output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)
+    # Use KDtree to find the peaks that are too close to each other
+    tree = cKDTree(coord)
+
+    indices = tree.query_ball_point(coord, r=spacing, p=p_norm)
+    rejected_peaks_indices = set()
+    for idx, candidates in enumerate(indices):
+        if idx not in rejected_peaks_indices:
+            # keep current point and the points at exactly spacing from it
+            candidates.remove(idx)
+            dist = distance.cdist([coord[idx]],
+                                  coord[candidates],
+                                  distance.minkowski,
+                                  p=p_norm).reshape(-1)
+            candidates = [c for c, d in zip(candidates, dist)
+                          if d < spacing]
+
+            # candidates.remove(keep)
+            rejected_peaks_indices.update(candidates)
+
+    # Remove the peaks that are too close to each other
+    output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)
+
+    return output
+
+
+def ensure_spacing(coords, spacing=1, p_norm=np.inf, min_split_size=50):
+    """Returns a subset of coord where a minimum spacing is guaranteed.
+
+    Parameters
+    ----------
+    coord : array_like
+        The coordinates of the considered points.
+    spacing : float
+        the maximum allowed spacing between the points.
+    p_norm : float
+        Which Minkowski p-norm to use. Should be in the range [1, inf].
+        A finite large p may cause a ValueError if overflow can occur.
+        ``inf`` corresponds to the Chebyshev distance and 2 to the
+        Euclidean distance.
+    min_split_size : int
+        Minimum split size used to process ``coord`` by batch to save
+        memory. If None, the memory saving strategy is not applied.
+
+    Returns
+    -------
+    output : array_like
+        A subset of coord where a minimum spacing is guaranteed.
+
+    """
+
+    output = coords
+    if len(coords):
+
+        coords = np.atleast_2d(coords)
+        if min_split_size is None:
+            batch_list = [coords]
+        else:
+            coord_count = len(coords)
+            split_count = int(np.log2(coord_count / min_split_size)) + 1
+            split_idx = np.cumsum(
+                [coord_count // (2 ** i) for i in range(1, split_count)])
+            batch_list = np.array_split(coords, split_idx)
+
+        output = np.zeros((0, coords.shape[1]), dtype=coords.dtype)
+        for batch in batch_list:
+            output = _ensure_spacing(np.vstack([output, batch]),
+                                     spacing, p_norm)
 
     return output

{"golden_diff": "diff --git a/skimage/_shared/coord.py b/skimage/_shared/coord.py\n--- a/skimage/_shared/coord.py\n+++ b/skimage/_shared/coord.py\n@@ -2,7 +2,7 @@\n from scipy.spatial import cKDTree, distance\n \n \n-def ensure_spacing(coord, spacing=1, p_norm=np.inf):\n+def _ensure_spacing(coord, spacing, p_norm):\n     \"\"\"Returns a subset of coord where a minimum spacing is guaranteed.\n \n     Parameters\n@@ -24,28 +24,72 @@\n \n     \"\"\"\n \n-    output = coord\n-    if len(coord):\n-        # Use KDtree to find the peaks that are too close to each other\n-        tree = cKDTree(coord)\n-\n-        indices = tree.query_ball_point(coord, r=spacing, p=p_norm)\n-        rejected_peaks_indices = set()\n-        for idx, candidates in enumerate(indices):\n-            if idx not in rejected_peaks_indices:\n-                # keep current point and the points at exactly spacing from it\n-                candidates.remove(idx)\n-                dist = distance.cdist([coord[idx]],\n-                                      coord[candidates],\n-                                      distance.minkowski,\n-                                      p=p_norm).reshape(-1)\n-                candidates = [c for c, d in zip(candidates, dist)\n-                              if d < spacing]\n-\n-                # candidates.remove(keep)\n-                rejected_peaks_indices.update(candidates)\n-\n-        # Remove the peaks that are too close to each other\n-        output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)\n+    # Use KDtree to find the peaks that are too close to each other\n+    tree = cKDTree(coord)\n+\n+    indices = tree.query_ball_point(coord, r=spacing, p=p_norm)\n+    rejected_peaks_indices = set()\n+    for idx, candidates in enumerate(indices):\n+        if idx not in rejected_peaks_indices:\n+            # keep current point and the points at exactly spacing from it\n+            candidates.remove(idx)\n+            dist = distance.cdist([coord[idx]],\n+                                  coord[candidates],\n+                                  distance.minkowski,\n+                                  p=p_norm).reshape(-1)\n+            candidates = [c for c, d in zip(candidates, dist)\n+                          if d < spacing]\n+\n+            # candidates.remove(keep)\n+            rejected_peaks_indices.update(candidates)\n+\n+    # Remove the peaks that are too close to each other\n+    output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)\n+\n+    return output\n+\n+\n+def ensure_spacing(coords, spacing=1, p_norm=np.inf, min_split_size=50):\n+    \"\"\"Returns a subset of coord where a minimum spacing is guaranteed.\n+\n+    Parameters\n+    ----------\n+    coord : array_like\n+        The coordinates of the considered points.\n+    spacing : float\n+        the maximum allowed spacing between the points.\n+    p_norm : float\n+        Which Minkowski p-norm to use. Should be in the range [1, inf].\n+        A finite large p may cause a ValueError if overflow can occur.\n+        ``inf`` corresponds to the Chebyshev distance and 2 to the\n+        Euclidean distance.\n+    min_split_size : int\n+        Minimum split size used to process ``coord`` by batch to save\n+        memory. If None, the memory saving strategy is not applied.\n+\n+    Returns\n+    -------\n+    output : array_like\n+        A subset of coord where a minimum spacing is guaranteed.\n+\n+    \"\"\"\n+\n+    output = coords\n+    if len(coords):\n+\n+        coords = np.atleast_2d(coords)\n+        if min_split_size is None:\n+            batch_list = [coords]\n+        else:\n+            coord_count = len(coords)\n+            split_count = int(np.log2(coord_count / min_split_size)) + 1\n+            split_idx = np.cumsum(\n+                [coord_count // (2 ** i) for i in range(1, split_count)])\n+            batch_list = np.array_split(coords, split_idx)\n+\n+        output = np.zeros((0, coords.shape[1]), dtype=coords.dtype)\n+        for batch in batch_list:\n+            output = _ensure_spacing(np.vstack([output, batch]),\n+                                     spacing, p_norm)\n \n     return output\n", "issue": "ensure_spacing function may be slow\n## Description\r\n\r\nThe `skimage._shared.coord.ensure_spacing` function introduced in #4760 may be slow when the number of input points is large.\r\n\r\n## Way to reproduce\r\n```python\r\nIn [1]: import numpy as np\r\n\r\nIn [2]: from skimage._shared.coord import ensure_spacing\r\n\r\nIn [3]: for n in range(500, 10001, 500):\r\n    ...:     print(f\"n = {n}\")\r\n    ...:     x = np.random.rand(n, 2)\r\n    ...:     %timeit ensure_spacing(x, 0.2)\r\n    ...: \r\nn = 500\r\n27.6 ms \u00b1 857 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10 loops each)\r\nn = 1000\r\n64.7 ms \u00b1 1.93 ms per loop (mean \u00b1 std. dev. of 7 runs, 10 loops each)\r\nn = 1500\r\n105 ms \u00b1 2.27 ms per loop (mean \u00b1 std. dev. of 7 runs, 10 loops each)\r\nn = 2000\r\n158 ms \u00b1 1.18 ms per loop (mean \u00b1 std. dev. of 7 runs, 10 loops each)\r\nn = 2500\r\n213 ms \u00b1 7.32 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 3000\r\n299 ms \u00b1 11.9 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 3500\r\n378 ms \u00b1 3.05 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 4000\r\n428 ms \u00b1 11.7 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 4500\r\n554 ms \u00b1 14 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 5000\r\n647 ms \u00b1 9.42 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 5500\r\n777 ms \u00b1 7.05 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 6000\r\n870 ms \u00b1 13.2 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 6500\r\n1.03 s \u00b1 9.56 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 7000\r\n1.17 s \u00b1 12.8 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 7500\r\n1.33 s \u00b1 28 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 8000\r\n1.45 s \u00b1 18.5 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 8500\r\n1.63 s \u00b1 36.6 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 9000\r\n1.87 s \u00b1 50.4 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 9500\r\n2.07 s \u00b1 23.3 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\nn = 10000\r\n2.29 s \u00b1 51.3 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\r\n```\r\n\n", "before_files": [{"content": "import numpy as np\nfrom scipy.spatial import cKDTree, distance\n\n\ndef ensure_spacing(coord, spacing=1, p_norm=np.inf):\n    \"\"\"Returns a subset of coord where a minimum spacing is guaranteed.\n\n    Parameters\n    ----------\n    coord : ndarray\n        The coordinates of the considered points.\n    spacing : float\n        the maximum allowed spacing between the points.\n    p_norm : float\n        Which Minkowski p-norm to use. Should be in the range [1, inf].\n        A finite large p may cause a ValueError if overflow can occur.\n        ``inf`` corresponds to the Chebyshev distance and 2 to the\n        Euclidean distance.\n\n    Returns\n    -------\n    output : ndarray\n        A subset of coord where a minimum spacing is guaranteed.\n\n    \"\"\"\n\n    output = coord\n    if len(coord):\n        # Use KDtree to find the peaks that are too close to each other\n        tree = cKDTree(coord)\n\n        indices = tree.query_ball_point(coord, r=spacing, p=p_norm)\n        rejected_peaks_indices = set()\n        for idx, candidates in enumerate(indices):\n            if idx not in rejected_peaks_indices:\n                # keep current point and the points at exactly spacing from it\n                candidates.remove(idx)\n                dist = distance.cdist([coord[idx]],\n                                      coord[candidates],\n                                      distance.minkowski,\n                                      p=p_norm).reshape(-1)\n                candidates = [c for c, d in zip(candidates, dist)\n                              if d < spacing]\n\n                # candidates.remove(keep)\n                rejected_peaks_indices.update(candidates)\n\n        # Remove the peaks that are too close to each other\n        output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)\n\n    return output\n", "path": "skimage/_shared/coord.py"}], "after_files": [{"content": "import numpy as np\nfrom scipy.spatial import cKDTree, distance\n\n\ndef _ensure_spacing(coord, spacing, p_norm):\n    \"\"\"Returns a subset of coord where a minimum spacing is guaranteed.\n\n    Parameters\n    ----------\n    coord : ndarray\n        The coordinates of the considered points.\n    spacing : float\n        the maximum allowed spacing between the points.\n    p_norm : float\n        Which Minkowski p-norm to use. Should be in the range [1, inf].\n        A finite large p may cause a ValueError if overflow can occur.\n        ``inf`` corresponds to the Chebyshev distance and 2 to the\n        Euclidean distance.\n\n    Returns\n    -------\n    output : ndarray\n        A subset of coord where a minimum spacing is guaranteed.\n\n    \"\"\"\n\n    # Use KDtree to find the peaks that are too close to each other\n    tree = cKDTree(coord)\n\n    indices = tree.query_ball_point(coord, r=spacing, p=p_norm)\n    rejected_peaks_indices = set()\n    for idx, candidates in enumerate(indices):\n        if idx not in rejected_peaks_indices:\n            # keep current point and the points at exactly spacing from it\n            candidates.remove(idx)\n            dist = distance.cdist([coord[idx]],\n                                  coord[candidates],\n                                  distance.minkowski,\n                                  p=p_norm).reshape(-1)\n            candidates = [c for c, d in zip(candidates, dist)\n                          if d < spacing]\n\n            # candidates.remove(keep)\n            rejected_peaks_indices.update(candidates)\n\n    # Remove the peaks that are too close to each other\n    output = np.delete(coord, tuple(rejected_peaks_indices), axis=0)\n\n    return output\n\n\ndef ensure_spacing(coords, spacing=1, p_norm=np.inf, min_split_size=50):\n    \"\"\"Returns a subset of coord where a minimum spacing is guaranteed.\n\n    Parameters\n    ----------\n    coord : array_like\n        The coordinates of the considered points.\n    spacing : float\n        the maximum allowed spacing between the points.\n    p_norm : float\n        Which Minkowski p-norm to use. Should be in the range [1, inf].\n        A finite large p may cause a ValueError if overflow can occur.\n        ``inf`` corresponds to the Chebyshev distance and 2 to the\n        Euclidean distance.\n    min_split_size : int\n        Minimum split size used to process ``coord`` by batch to save\n        memory. If None, the memory saving strategy is not applied.\n\n    Returns\n    -------\n    output : array_like\n        A subset of coord where a minimum spacing is guaranteed.\n\n    \"\"\"\n\n    output = coords\n    if len(coords):\n\n        coords = np.atleast_2d(coords)\n        if min_split_size is None:\n            batch_list = [coords]\n        else:\n            coord_count = len(coords)\n            split_count = int(np.log2(coord_count / min_split_size)) + 1\n            split_idx = np.cumsum(\n                [coord_count // (2 ** i) for i in range(1, split_count)])\n            batch_list = np.array_split(coords, split_idx)\n\n        output = np.zeros((0, coords.shape[1]), dtype=coords.dtype)\n        for batch in batch_list:\n            output = _ensure_spacing(np.vstack([output, batch]),\n                                     spacing, p_norm)\n\n    return output\n", "path": "skimage/_shared/coord.py"}]}