Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [metric-spaces]

The tag has no usage guidance.

0
votes
0answers
62 views

Points of a finite set wihtin a ball

I am looking for data-structures to store efficiently a set of points $E$ in an euclidean space of dimension $d$. In particular, I would like to be able to solve the problem of finding all the point ...
3
votes
0answers
78 views

Do features always induce a metric?

It is well-known in functional analysis that an inner product always induces a norm and a norm always induces a metric, and the reverse directions do not hold in general. I am wondering if a similar ...
1
vote
0answers
35 views

BK-Tree intersection

I'm looking to calculate the approximate intersection (proximity under a certain distance) of two sets of points in a discrete metric space. In other words, given a metric space $(M, d)$, subsets $A, ...
1
vote
1answer
82 views

Subclasses or characterizations of modular or pseudo-modular planar graphs

We say that a graph G is modular if for every three vertices x,y,z there exists a vertex w that lies on a shortest path between every two of x, y, z. Pseudo-modular (or "3-Helly") graphs are defined ...
0
votes
1answer
148 views

A metric space on Turing machines

Let $L$ be a decidable language. Let $X^L$ be the set of deterministic Turing machines which decide $L$. Define two machines $A,B\in X^L$ to be time-equivalent if $t_A(w) = t_B(w)$ for all $w \in \...
3
votes
0answers
101 views

Embedding distortion under group quotient

The high level question is as follows: Suppose some group (here assumed to be a vector space of $\mathbf{F}_2^n$) has a low-distortion embedding into $l_1$. Under what condition does the quotient of ...
3
votes
2answers
154 views

Are there Similar Distance Binary Error Correcting Codes?

I'm trying to find a low distortion embedding of the trivial metric space into hamming space. It seems this should be doable by using a large set of low dimensional vectors, with approximately equal ...
11
votes
1answer
222 views

Compute lowest dimensional polytope from a given set of sign vectors

Given a set of hyperplanes determined by the normal vectors $h_1,\dots,h_m \in \mathbf R^d$, its cell types (or sign vectors) are all vectors $t\in\{+,-\}^m$ for which there exists a vector $v\in\...
3
votes
0answers
93 views

Approximation of covering number in metric space

Consider the following setting: Let $(X,d)$ be a metric space and let $S$ be a finite subset of $X$. An $\epsilon$-cover of $S$ is any subset $C\subset S$ such that $$ \max_{x\in S} d(x,C)\leq \...
5
votes
2answers
138 views

L1 - embeddability of metrics supported on the Hypercube

I am quite new to the area of metric embeddings so this question might turn out to be extremely easy. Consider a metric supported on the edges of a boolean hypercube. By supported I mean every edge ...
1
vote
0answers
88 views

Are there any polynomial cases of Balanced Minimum Evolution?

The BME problem has an interest in computational biology, for the reconstruction of phylogenetic trees from a distance matrix. Let me provide some context before defining the problem. Suppose that we ...
0
votes
1answer
59 views

Define metric for systems of set of points

Given a set of points $p_1, p_2, ..., p_n$ and a collection of sets from $n$ points $S_1, S_2,...,S_m$. The pairwise distance between any three points $(p_1, p_2, p_3)$ satisfies triangle inequality $...
1
vote
0answers
45 views

Fixed orientation metrics

I am currently working on some computational geometry problems with non-euclidean metrics, and have some trouble on a fact that sounds easy enough, at least intuitively. The fact is as follows: ...
2
votes
0answers
113 views

Quality measure for clusters of a metric space embedding of a graph?

When evaluating clustering algorithms for networks, we have well-established metrics like Modularity and Surprise for evaluating the quality of the resulting partition. If we then embed our graph (...
3
votes
1answer
1k views

Non-metric distances

Could anybody suggest practically important distances that are significantly non-metric and are not Bregman divergences? For instance, they are non-symmetric and not equivalent to the Euclidean ...
2
votes
1answer
370 views

An intuitive justification - Metric Embedding Based Approximation Algorithms

Recently, I started (independent) learning of the theory of metric embeddings from the Fall 2003 course offered at CMU . I had a very basic question from the very first lecture of this course ...
1
vote
1answer
71 views

Term for a correspondence of two point sets regarding their ordering in each dimension

Let there be two sets of points $S$ and $S'$ in $R^d$. $|S| = |S'|$, and for each point $s_i$ in $S$ it exists exactly one corresponding point $s'_i$ in $S'$, such that the ordering of ...
6
votes
1answer
200 views

Has anyone studied “polynomially compact” metric spaces?

A subspace $S$ of a metric space $A$ is compact if it is complete and totally bounded. Here, complete means that every Cauchy sequence in $S$ has a limit also in $S$. For $S$ to be totally bounded, ...
4
votes
1answer
178 views

Need a term for a graph-theoretic/metric concept

Let $(X,d)$ be a metric space, and define $\rho$ to be the largest distance of any $x\in X$ to its nearest neighbor. Formally, $$ \rho = \sup_{x \in X}~ d(x, X \setminus \{x\}). $$ Does this ...
15
votes
1answer
564 views

Fixed point theorems for constructive metric spaces?

Banach's fixed point theorem says that if we have a nonempty complete metric space $A$, then any uniformly contractive function $f : A \to A$ it has a unique fixed point $\mu(f)$. However, the proof ...
11
votes
1answer
298 views

Is Escardó's metric semantic for PCF+timeouts fully abstract ?

In his 1999 workshop paper "A Metric Model of PCF", Martín Escardó showed that it is possible to give a simple interpretation of PCF in the category of complete ultrametric spaces and ...