The bisector of two nonempty sets P and Q in a metric space is the set of all points with equal distance to P and to Q. A distance k-sector of P and Q, where k ≥ 2 is an integer, is a (k-1)-tuple (C1, C2, ..., Ck-1) such that Ci is the bisector of Ci-1 and Ci+1 for every i= 1, 2, ..., k-1, where C0 = P and Ck = Q. This notion, for the case where P and Q are points in Euclidean plane, was introduced by Asano, Matousek, and Tokuyama, motivated by a question of Murata in VLSI design. They established the existence and uniqueness of the distance trisector in this special case. We prove the existence of a distance k-sector for all k and for every two disjoint, nonempty, closed sets P and Q in Euclidean spaces of any (finite) dimension, or more generally, in proper geodesic spaces (uniqueness remains open). The core of the proof is a new notion of k-gradation for P and Q, whose existence (even in an arbitrary metric space) is proved using the Knaster-Tarski fixed point theorem, by a method introduced by Reem and Reich for a slightly different purpose.

No abstract available.

Regular triangulationsform a meaningful wide subclass of triangulations of points in general dimensions.They can be defined as a natural extension of the Delaunay triangulation and also of lexicographic triangulations, a subclass of triangulations well-known in the theory

No abstract available.

This paper considers the maximin placement of a convex polygon P inside a polygon Q, and introduce several new static and dynamic Voronoi diagrams to solve the problem. It is shown that P can be placed inside Q, using translation and rotation, so that the minimum Euclidean distance between any point on P and any point on Q is maximized in Ο(m4n λ16(mn) log mn) time, where m and n are the numbers of edges of P and Q, respectively, and λ16(N) is the maximum length of Davenport-Schinzel sequences on N alphabets of order 16. If only translation is allowed, the problem can be solved in Ο(mn log mn) time. The problem of placing multiple translates of P inside Q in a maximum manner is also considered, and in connection with this problem the dynamic Voronoi diagram of κ rigidly moving sets of n points is investigated. The combinatorial complexity of this canonical dynamic diagram for κn points is shown to be Ο(n2) and Ο(n3κ4 log* κ) for κ = 2, 3 and κ ≥ 4, respectively. Several related problems are also treated in a unified way.

No abstract available.

This paper presents algorithms for approximating a set of n points by a linear function, or a line, that minimizes the L1 norm of vertical and orthogonal distances. The algorithms find exact solutions based upon geometric properties of the problems as opposed to approximate solutions based upon existing numerical techniques. The algorithmic complexity of these problems appears not to have been investigated before our work in [9], although Ο(n3) naive algorithms can be easily obtained based on some simple characteristics of optimal L1 solutions. In this paper, an Ο(n) optimal time algorithm for the weighted vertical L1 problem is presented. The algorithm is based upon a modified multi-dimensional search technique which extends the applicability of the basic technique to a wider class of problems. An Ο(n1.5 log2 n) algorithm is presented for the unweighted orthogonal problem, and an Ο(n2) algorithm is presented for the weighted problem. An Ω(n log n) lower bound for the orthogonal L1 problem is shown under a certain model of computation. Also, the complexity of solving the orthogonal L1 problem is related to the construction of the k-belt of an arrangement of lines.