This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
unsolved_puzzles [2019/02/02 00:35] – [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 | ||
---|---|---|---|
Line 31: | Line 31: | ||
===== 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// ∈ [// | + | 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// ∈ [// |
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 ||τ(// | 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 ||τ(// | ||
Line 118: | Line 118: | ||
===== Shortest-path-preserving rounding of weights in a graph ===== | ===== Shortest-path-preserving rounding of weights in a graph ===== | ||
- | (updated | + | (updated |
* 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 // | * any shortest path in //G// is a shortest path in // | ||
Line 127: | Line 127: | ||
* **Embedding cues about travel time in schematic maps.**\\ By Herman Haverkort.\\ Presented at the //Schematic Mapping Workshop 2014//.\\ {{research:: | * **Embedding cues about travel time in schematic maps.**\\ By Herman Haverkort.\\ Presented at the //Schematic Mapping Workshop 2014//.\\ {{research:: | ||
- | 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 | + | 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)//, | ||
+ | |||
+ | |||
+ | 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. | ||