| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| unsolved_puzzles [2019/02/02 00:32] – [Nearest-neighbour-preserving space-filling curves] administrator | unsolved_puzzles [2023/09/05 11:23] (current) – [A lower bound on the dilation of plane-filling curves] administrator |
|---|
| ===== A lower bound on the dilation of plane-filling curves ===== | ===== A lower bound on the dilation of plane-filling curves ===== |
| |
| Let τ: [0,1] → //T// be a continuous surjection to a compact set //T// in the plane such that for any //a// ≤ //b// ∈ [0,1], the union of τ(//t//) over all //t// ∈ [//a//,//b//] has two-dimensional Lebesgue measure //b//−//a//. | Let τ: [0,1] → //T// be a continuous surjection to a compact set //T// in the plane such that for any //a// ≤ //b// ∈ [0,1], the union of τ(//t//) over all //t// ∈ [//a//,//b//] has two-dimensional Jordan measure //b//−//a//. |
| In other words, τ is a measure-preserving plane-filling curve. The dilation of the curve is the maximum, over all //a// < //b// ∈ [0,1], of ||τ(//a//)τ(//b//)||² / (//b//−//a//), where ||τ(//a//)τ(//b//)|| is the Euclidean distance between τ(//a//) and τ(//b//). Prove a tight lower bound on the smallest possible dilation for any measure-preserving plane-filling curve. | In other words, τ is a measure-preserving plane-filling curve. The dilation of the curve is the maximum, over all //a// < //b// ∈ [0,1], of ||τ(//a//)τ(//b//)||² / (//b//−//a//), where ||τ(//a//)τ(//b//)|| is the Euclidean distance between τ(//a//) and τ(//b//). Prove a tight lower bound on the smallest possible dilation for any measure-preserving plane-filling curve. |
| |
| Suppose we have //k// functions //f//<sub>1</sub>,...,//f//<sub>//k//</sub> from [0,1]<sup>//d//</sup> to [0,1] that have some favourable properties, which I will explain shortly. Now, given any set of //n// distinct points //S//⊂[0,1]<sup>//d//</sup>, we can construct //k// ordered lists //S//<sub>1</sub>,...,//S//<sub>//k//</sub>, such that //S//<sub>//i//</sub> contains the points of //S// in order of increasing image under //f//<sub>//i//</sub>. For any point //p// in //S//, let //N(S,p)// be the set of at most 2//k// points that consists of the immediate predecessors and successors of //p// in //S//<sub>1</sub>,...,//S//<sub>//k//</sub>. The favourable property that we are looking for is this: there is a constant φ (which may depend on //d//), such that, regardless of the choice of //S// and //p//, the L<sub>∞</sub>-distance between //p// and the nearest point in //N(S,p)// is at most φ times the L<sub>∞</sub>-distance between //p// and the nearest point in //S//\{//p//}. What are the best bounds on //k// and φ, as a function of //d//, that can we realize? | Suppose we have //k// functions //f//<sub>1</sub>,...,//f//<sub>//k//</sub> from [0,1]<sup>//d//</sup> to [0,1] that have some favourable properties, which I will explain shortly. Now, given any set of //n// distinct points //S//⊂[0,1]<sup>//d//</sup>, we can construct //k// ordered lists //S//<sub>1</sub>,...,//S//<sub>//k//</sub>, such that //S//<sub>//i//</sub> contains the points of //S// in order of increasing image under //f//<sub>//i//</sub>. For any point //p// in //S//, let //N(S,p)// be the set of at most 2//k// points that consists of the immediate predecessors and successors of //p// in //S//<sub>1</sub>,...,//S//<sub>//k//</sub>. The favourable property that we are looking for is this: there is a constant φ (which may depend on //d//), such that, regardless of the choice of //S// and //p//, the L<sub>∞</sub>-distance between //p// and the nearest point in //N(S,p)// is at most φ times the L<sub>∞</sub>-distance between //p// and the nearest point in //S//\{//p//}. What are the best bounds on //k// and φ, as a function of //d//, that can we realize? |
| | |
| **What is known?** For even //d//, if we choose //k//=//d//+1 and each //f//<sub>//i//</sub> such that its inverse //f//<sub>//i//</sub><sup>−1</sup> is, for example, a //d//-dimensional Hilbert curve or Z-order traversal of the cube [−1+i/(//d//+1),1+i/(//d//+1)]<sup>//d//</sup>, then we get approximation ratio φ≤2(//d//+1) (Liao et al.((Swanwa Liao, Mario López, and Scott Leutenegger: High dimensional similarity search with space filling curves. {{https://doi.org/10.1109/ICDE.2001.914876|ICDE 2001:615-622}}. In fact, Liao et al. only prove an approximation ratio φ≤4(//d//+1), but we can improve that to φ≤2(//d//+1). Proof sketch: let //p// be a point in //S//, let //q// be a nearest neighbour to //p// in //S//, and let //x// be the distance between //p// and //q//. For each recursion level //r// there is a permutation π such that cubes of width 2<sup>−//r//</sup> at offset 2<sup>−//r//</sup>·//i///(//d//+1) (mod 2<sup>−//r//</sup>) in all //d// coordinates are contiguous in the ordering induced by //f//<sub>π(//i//)</sub>; in particular if we choose //r// such that 2<sup>−//r//</sup> is more than (//d//+1)//x// and at most (2//d//+2)//x//. Since the point //c// = ½(//p//+//q//) has only //d// coordinates, there must an //i// such that all coordinates of //c// differ from 2<sup>−//r//</sup> //i///(//d//+1) by at least 2<sup>−//r//</sup>/(2//d//+2) (mod 2<sup>−//r//</sup>). Thus //c// is at distance at least 2<sup>−//r//</sup>/(2//d//+2) > ½//x// from the boundary of a contiguous cube of width 2<sup>−//r//</sup> in the ordering induced by //f//<sub>π(//i//)</sub>. The points //p// and //q// in //S// lie in that same cube. So at least one of the neighbours of //p// in //S//<sub>π(//i//)</sub> also lies in that same cube and is a (2//d//+2)-approximation to the nearest neighbour of //p// in //S//.))) | **What is known?** For even //d//, if we choose //k//=//d//+1 and each //f//<sub>//i//</sub> such that its inverse //f//<sub>//i//</sub><sup>−1</sup> is, for example, a //d//-dimensional Hilbert curve or Z-order traversal of the cube [−1+i/(//d//+1),1+i/(//d//+1)]<sup>//d//</sup>, then we get approximation ratio φ≤2(//d//+1) (Liao et al.((Swanwa Liao, Mario López, and Scott Leutenegger: High dimensional similarity search with space filling curves. {{https://doi.org/10.1109/ICDE.2001.914876|ICDE 2001:615-622}}. In fact, Liao et al. only prove an approximation ratio φ≤4(//d//+1), but we can improve that to φ≤2(//d//+1). Proof sketch: let //p// be a point in //S//, let //q// be a nearest neighbour to //p// in //S//, and let //x// be the distance between //p// and //q//. For each recursion level //r// there is a permutation π such that cubes of width 2<sup>−//r//</sup> at offset 2<sup>−//r//</sup>·//i///(//d//+1) (mod 2<sup>−//r//</sup>) in all //d// coordinates are contiguous in the ordering induced by //f//<sub>π(//i//)</sub>; in particular if we choose //r// such that 2<sup>−//r//</sup> is more than (//d//+1)//x// and at most (2//d//+2)//x//. Since the point //c// = ½(//p//+//q//) has only //d// coordinates, there must an //i// such that all coordinates of //c// differ from 2<sup>−//r//</sup> //i///(//d//+1) by at least 2<sup>−//r//</sup>/(2//d//+2) (mod 2<sup>−//r//</sup>). Thus //c// is at distance at least 2<sup>−//r//</sup>/(2//d//+2) > ½//x// from the boundary of a contiguous cube of width 2<sup>−//r//</sup> in the ordering induced by //f//<sub>π(//i//)</sub>. The points //p// and //q//, at distance ½//x// from //c//, lie in that same cube. So at least one of the neighbours of //p// in //S//<sub>π(//i//)</sub> also lies in that same cube and is a (2//d//+2)-approximation to the nearest neighbour of //p// in //S//.))) |
| |
| The first questions: Can we prove that φ must be Ω(//d//) if //k//=//d//+1? Given any fixed (even) //d// and //k//=//d//, is there a set of functions //f//<sub>1</sub>,...,//f//<sub>//d//</sub> such that φ can be bounded? Or can we prove that φ cannot be bounded if //k//=//d//? | The first questions: Can we prove that φ must be Ω(//d//) if //k//=//d//+1? Given any fixed (even) //d// and //k//=//d//, is there a set of functions //f//<sub>1</sub>,...,//f//<sub>//d//</sub> such that φ can be bounded? Or can we prove that φ cannot be bounded if //k//=//d//? |
| ===== Shortest-path-preserving rounding of weights in a graph ===== | ===== Shortest-path-preserving rounding of weights in a graph ===== |
| |
| (updated 17 January 2019) Prove the NP-hardness or give an efficient algorithm for the following problem: given a weighted undirected planar graph //G// with non-negative weights, in which each edge is a shortest path, decide whether one can construct a copy //G'// of //G// in which all weights are replaced by integers, such that the following conditions hold: | (updated 25 September 2019) Prove the NP-hardness or give an efficient algorithm for the following problem: given a weighted undirected planar graph //G// with non-negative weights, in which each edge is a shortest path, decide whether one can construct a copy //G'// of //G// in which all weights are replaced by integers, such that the following conditions hold: |
| * the difference in weight between any shortest path in //G// and the corresponding path in //G'// is less than 1; | * the difference in weight between any shortest path in //G// and the corresponding path in //G'// is less than 1; |
| * any shortest path in //G// is a shortest path in //G'//. | * any shortest path in //G// is a shortest path in //G'//. |
| * **Embedding cues about travel time in schematic maps.**\\ By Herman Haverkort.\\ Presented at the //Schematic Mapping Workshop 2014//.\\ {{research::haverkort-cues-about-travel-time.pdf|text}} (draft of full report). | * **Embedding cues about travel time in schematic maps.**\\ By Herman Haverkort.\\ Presented at the //Schematic Mapping Workshop 2014//.\\ {{research::haverkort-cues-about-travel-time.pdf|text}} (draft of full report). |
| |
| We believe we have found a proof that the problem is, in general, NP-hard for non-planar graphs, and we believe we have found a polynomial-time algorithm that solves the problem for trees---we are currently writing up these results. However, from an application point of view, the case of planar graphs may be more relevant, and for planar graphs we still do not know. | The problem is, in general, NP-hard for non-planar graphs, and can be solved in polynomial time for trees: |
| | |
| | * **Shortest-Path-Preserving Rounding.**\\ By Herman Haverkort, David Kübel, and Elmar Langetepe.\\ //Computing Research Repository (arXiv.org)//, 1905.08621, 2019.\\ [[https://arxiv.org/abs/1905.08621|text]] |
| | |
| | |
| | However, from an application point of view, the case of planar graphs may be more relevant, and for planar graphs we still do not know. |
| |
