1
vote
What is the problem in "closest pair problem" if all points share the same x-coordinate
Without the assumption that no points share the same x-coordinate, we run into one of two problems:
One problem occurs if you partition the space by x-coordinate. Say all points have the same x-...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
ds.algorithms × 1754graph-algorithms × 323
graph-theory × 273
cc.complexity-theory × 242
reference-request × 232
approximation-algorithms × 156
optimization × 108
co.combinatorics × 107
ds.data-structures × 100
time-complexity × 88
np-hardness × 60
linear-algebra × 59
linear-programming × 59
cg.comp-geom × 57
sorting × 52
randomized-algorithms × 49
sat × 43
matrices × 43
lower-bounds × 32
heuristics × 30
nt.number-theory × 29
counting-complexity × 28
directed-acyclic-graph × 28
machine-learning × 27
complexity-classes × 26