• Tetsuo Asano (JAIST, Japan)
  • Title: Three unsolved problems
  • Abstract:

    This talk includes three problems which I have been attacking without any definite results.

    The first unsolved problem is "online uniformity of points" to seek for an optimal sequence of points to achieve good uniformity at every instance. Designing such an optimal sequence on a line is rather easy, but it is hard to decide whether we can determine any ordering of given points so that the uniformity is always at least some fixed value. It is not known whether it is NP-hard.

    The second unsolved problem is "optimal embedding of unit distance sets" which is to find a point configuration $P$ of $n$ points in the plane so that the potential function $f_{p,q}(P)$ is minimized, where $f_{p, q}(P)= Σ_{i<j}|d(p_i, p_j)^p - 1|^q$ and $d(,)$ is the Euclidean distance.

    Experimental results show some interesting features.

    For $f_{1,2}$, an optimal embedding is achieved by locating points on a few circles.

    For $f_{2,1}$, three multiple points may achieve optimal embedding.

    For $f_{2,2}$, if points are located on a circle it looks optimal.

    The third unsolved problem is "optimal aspect-ratio triangulation" that is to find an optimal triangulation of points in the plane in the sense that the worst aspect ratio of the resulting triangles is the largest among all possible triangulations. It is not known whether there is a polynomial-time algorithm.