Solution :

The myopic visibility complex lies in the space of free line segments of length exactly 1 or that are maximal and length at most 1.

This space is not a subspace of that of the normal visibility complex, nor is the converse true. A segment of length 1 that touches no object is in the myopic visibility complex but not in the normal visibility complex. A bitangent of length more than 1 is in the normal visibility complex but not in the myopic visibility complex.

Two segments are in the same cell of the myopic visibility complex if they see and are tangent to the same objects. Notice that there are cells of dimension 3 in the myopic visibility complex (set of free segments of length 1) whereas the maximum dimension cell in the normal visibility complex is 2. The set of segments tangent to one object is a torus - you can either slide the segment or rotate it. (How do you know it's a torus and not a klein bottle?)

There is an algorithm that computes the 1-myopic visibility complex in time at most log n times the size of the 2-myopic visibility complex when the objects are small. The idea is to cover the plane with a set of overlapping boxes of size 2 such that every segment of length at most 1 lies entirely in some box. Compute the visibility complex inside the boxes. Where does the logn come into it?

Solution :

Checking whether the myopic visibility graph is empty can be done in O(n\log n) time by finding the 2 closest points (compute the delaunay triangulation and then the distance between each pair of delaunay neighbors). Computing the myopic visibility of a set of points can be done in O(n log n + k) - replace all points by unit circles and search for intersections using a plane sweep.

The myopic visibility graph can be computed by first computing the normal visibility graph in time O(nlog n + l) time, then compute the distance between each visible pair; there are l of them. Since the myopic visibility graph is smaller than the normal one, k < l. So the challenge is to find the myopic visibility graph without first computing the normal one.

A subgraph of the myopic visibility graph, the Glisse graph, otherwise known as the Gabriel graph, can be computed from the Voronoi diagram : keep all dual edges between two objects such that the distance between these objects is less than one and such that a segment realizing this distance doesn't intersect a third Voronoi cell. The connected components of the Glisse graph are exactly the connected components of the myopic visibility graph. In other words, a minimum spanning forest of the myopic visibility graph can be computed in O(n log n) time. The myopic visibility graph can be computed by adding an edge ac whenever ab and bc are already in the graph and myopically visible. But that is somewhat quadratic.

A sub-problem that is interesting is - how fast can you test whether 2 objects are myopically visible ?

Solution : This is the same problem as - can every planar graph be realized as a unit distance graph with no crossings. It is true if points are replaced by disks.

This is false for trees having vertices whose degree is larger than five. For maximal outerplanar graphs it is false when the maximum degree is more than 10 and true when it is 4.

There exists a maximal outerplanar graph having maximum vertex degree at most nine that is not realizable.

Here is a little draft from Xavier and Beppe - 25 March. Unit distance graphs.

Solution : If you compute the visibility polygon first and then intersect it with a circle this gives a O(n) time algorithm. To answer the query version, use a combination of circular ray shooting and the O(k log n) time algorithm for the visibility polygon. This gives, after O(n log n) circular and normal ray shooting preprocessing time and space,O(k log^2 n) query time. k is the size of the output.

The O(k log n) algorithm works as follows : Shoot a ray from point p and start walking along the edge. At each vertex shoot a ray from p to see if its still visible. If it is not visible, start walking backward from the visible edge. Otherwise the whole edge is visible. Look at the next edge. If it goes behind, shoot a ray from the vertex further out, etc. For the myopic case, shoot a circular ray whenever you are distance 1 away.

Solution : See the paper "Base station coverage problems for geometric point sets" on Hervé's web page!!

There is a O(n^4) dynamic programming type algorithm to find the positions given a fixed line. It also works for squares in O(n^2 log n) and when the cost function is the sum of some power of the width of the squares. For unit discs an O(nlog n) algorithm was already known. Probably also can be made to work for boxes and 2 parallel or orthogonal segments.

Beppe's conjecture : An optimal horizontal line either contains a carrot, passes through the midpoint of two carrots or through the center of a circle defined by three carrots. This conjecture is true for 3 points, unresolved for 4 points and false for more than 4 points.

At the wrap-up session Helmut showed how to find a 2-approximation in O(nlog n) time. But then, according to Jon, at breakfast it slipped to a 4x approximation. (An example for which Helmut's algorithm does not give a 2x approximation is the case of two points at unit height and separation 2 + \epsilon.)

Here is another contribution from Jon - Feb 24, updated Feb 28, and again March 15.

"Here is a short write-up with an analysis of the two algorithms of Helmut's leading to a constant factor approximation in the line location problem for carrot watering. The two algorithms process the points (carrots) in order of decreasing distance from the line L - the first places two squares with edges abutting, with corners at the point being processed, the second places one square centered about the projection of the point on L. According to my analysis, the first algorithm gives a factor 4 approximation, the second a factor 3 approximation." Analysis of Helmut Algorithms.

Solution : Sandor thinks its NP-hard.

Solution : Estie's magic circle (EMC) is the minimum radius enclosing circle. If c <=4 EMC will be optimal. EMC will be a c/4-approximation for c>4. Sandor thinks its NP-hard for some c>4. Can be approximated up to a constant 4ish using Arora type technique.

Here is a write-up by Jon on the c=4 case.

There is also a limited visibility version of this.

At the wrap-up session Sandor proposed this variant : Given n points, find k points at which to place discs that cover the n points. The discs have radii r_1 ... r_k. The function to optimize to minimize the sum of r_i^alpha, where alpha >= 1. This should be NP-hard when alpha > 1, maybe NP-hard when alpha = 1 and should have a (1+ epsilon) PTAS.

Sue : The where are you problem. Given a set of polylines and a simple polygon, find a point p inside the polygon so that the myopic view from this point is exactly the given set of polylines.

Beppe : Which planar graphs can be realized as a local Delaunay triangulation?

Jon : Given an initial and final configuration of a set of coins, what is the maximum number of moves that you need to move the coins from the initial to the final configuration. The answer is between 3n/2 and 2n. There was some attempt to define a limited visibility version of this.

Sandor : How many unit squares can you pack into a simple rectilinear polygon with no overlap allowed ? Can it be solved in polynomial time?