Jean-Marie -Emmanuel Hyon

Alain Jean-Marie

Emmanuel Hyon
email: emmanuel.hyon@u-paris10.fr.

Scheduling in a queuing system with impatience and setup costs

Keywords: Scheduling, queuing system, impatience, deadline, optimal control, Markov decision processes

We consider a single server queue in discrete time, in which customers must be served before some limit sojourn time of geometrical distribution. A customer who is not served before this limit leaves the system: it is impatient. The fact of serving customers and the fact of losing them due to impatience induce costs. The purpose is to decide when to serve the customers so as to minimize costs. We use a Markov Decision Process with infinite horizon and discounted cost. We establish the structural properties of the stochastic dynamic programming operator, and we deduce that the optimal policy is of threshold type. In addition, thanks to a pathwise comparison analysis of two threshold policies, we are able to compute explicitly the optimal value of this threshold according to the parameters of problem.

Politique de service optimal dans une file d'attente en temps discret avec impatiences

Résumé : Nous considérons un modèle d'une file d'attente à un serveur en temps discret, dans laquelle les clients doivent être servis avant une durée de séjour limite, de distribution géométrique. Un client qui n'est pas servi avant cette limite quitte le système: il est impatient. Le fait de servir les clients et le fait de perdre des clients par impatience induisent des coûts. Il s'agit de décider de fac ¸on optimale quand servir les clients. Nous utilisons un processus de décision Markovien à horizon infini et à coûts actualisés. Nous établissons les propriétés structurelles de l'opérateur de programmation dynamique stochastique, et nous déduisons que la politique optimale est à seuil. Par ailleurs, grâce à une analyse trajectorielle comparative de deux politiques à seuil, nous calculons explicitement la valeur optimale de ce seuil en fonction des paramètres du problème.

Mots-clés : Ordonnancement, file d'attente, impatience, échéance, contrôle optimal, processus de décision markovien

Introduction

In this paper we are interested in the optimal control of a queuing system with impatient customers (or, equivalently said, customers with deadlines). The set-up of customer services, the storage of the customers in the queue as well as their departure from the queue due to impatience (called "losses" in the remainder of this paper) induce some costs and it has to be decided when to begin the service in order to minimize these costs. This is a genuine tradeoff problem, since instantaneous costs associated with the decisions serve/not serve are not constant: there is no reason a priori why the decision should be the same whatever the state of the system. Controlled queuing models, deterministic as well as stochastic, have been largely studied in the literature since their application fields are numerous: networking (see [START_REF] Altman | Handbook of Markov Decision Processes Methods and Applications, chapter Applications of Markov Decision Processes in Communication Networks : a survey[END_REF] and references therein), resources allocation (see [START_REF] Kleywegt | The dynamic and stochastic knapsack problem[END_REF] and references therein) to quote just a few. Nevertheless most of these works do not consider impatient customers but rather losses due to overflow. Yet, the phenomenon of impatience, associated with deadlines or "timeouts", has become non negligible in several fields: cellular communication networks [START_REF] Resende | Handbook of optimization in telecommunications[END_REF][START_REF] Artalejo | On the impact of customer balking, impatience and retrials in telecommunication systems[END_REF], call center [START_REF] Koole | Queueing models of call centers: An introduction[END_REF], yield management or reservations problems (see [START_REF] Papastavrou | The dynamic and stochastic knapsack problem with deadlines[END_REF] for discrete-time finite-horizon problems), real-time systems etc.

The literature features papers on the performance evaluation of queues with impatience, but relatively few on optimal control of such queues. One branch, represented by [START_REF] Bhattacharya | Optimal scheduling with strict deadlines[END_REF][START_REF] Towsley | On the optimality of minimum laxity and earliest deadline scheduling for real-time multiprocessors[END_REF], is concerned with finding the optimal scheduling algorithm so as to minimize deadline misses. Another direction is to consider the optimal routing between several queues [START_REF] Movaghar | Optimal control of parallel queues with impatient customers[END_REF][START_REF] Kocaga | Admission control for a multi-server queue with abandonment[END_REF], still in order to minimize average deadline overrun. In the present paper, our focus is on the influence of set-up costs: we consider that serving customers has a cost, which adds up to the costs of missing deadlines and holding customers. On the other hand, the question of the order of service is not relevant to us, since we assume that deadlines have a memoryless distribution.

Our longer-term objective is to solve the same problem but with batch service. The problem of optimally controlling a batch server in a queue (without impatience) has been addressed in [START_REF] Deb | Optimal control of batch service queues[END_REF] and [START_REF] Papadaki | Exploiting structure in adaptative dynamic programming algorithms for a stochastic batch service problem[END_REF] (see also the references therein). Its resolution is based on the Markov Decision Process (MDP) formalism, and goes through establishing some structural properties of the value function and the dynamic programming operator. This then allows to deduce some properties of the optimal policy, which in turns implies that the solution is a threshold (or control limit) policy. Unhappily, it appears that extending the techniques developed in [START_REF] Papadaki | Exploiting structure in adaptative dynamic programming algorithms for a stochastic batch service problem[END_REF] to queues with impatience is not straightforward. Indeed, it has been noted in [START_REF] Koole | Monotonicity in markov reward and decision chains: Theory and applications[END_REF] (quoted in [START_REF] Kocaga | Admission control for a multi-server queue with abandonment[END_REF]) that impatience tends to destroy the structural properties that are commonly used for proving the optimality of threshold policies. The importance of structural properties in the study of admission control policy and optimality proofs has been underlined in [START_REF] Glasserman | Monotone Structure in Discrete-Event Systems[END_REF]. In this paper, we show that structural properties exist although losses under given conditions on the value function and present the solution for service batches of unit size. For this purpose, we use some tools which, in our opinion, will be useful for solving more complex cases.

More precisely, in this work, we adapt the framework of structural analysis of Markov Decision Processes, as described for instance in [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF]. We adopt the infinite-horizon, discounted cost criterion. We establish the structural properties of the stochastic dynamic programming operator and we show that the optimal policy is a threshold policy. Furthermore, using a sample path comparison between policies with different values of the threshold, we explicitly compute the threshold value as a function of the parameters, and we conclude that the optimal policy is actually "always serve" or "never serve", based on a simple criterion derived from the cost parameters. We discuss in our conclusion some problems encountered with general batch sizes.

This paper is organized as follows: Section 2 deals with the model, while Section 3 establishes the structural properties and 4 focuses on the effective computations of the threshold.

Model

We consider a discrete time (or slotted) model, where the slot is the time unit. Customers are assumed to arrive at the beginning of each slot. 1 They are stored in an infinite buffer in which they wait for to be admitted in the server to be processed. This admission decision is made by a controller. The beginning of a new service induces a cost (for example a setup cost). Holding customers in the buffer also induces a cost. The service duration is assumed to be equal to the duration of a slot.

Customers are impatient: while they are in the buffer, they can leave spontaneously the system with fixed probability α, independently from the past and from each other. On the other hand, customers admitted in service are not impatient anymore. Each time a customer leaves the buffer, this induces a cost.

System dynamics

We proceed with introducing some additional notation, and formulating the optimal control problem in the framework of Markov Decision Processes, using the notation of Puterman [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF].

Assume that slots are numbered from 0 and denote with A n the number of arrivals at the beginning of slot n. The sequence {A n } n∈N is assumed to be an i.i.d. sequence of random variables. With the usual abuse of notation, we denote generically this common distribution with A. We furthermore assume that A is of mean λ, so that the arrival process is of intensity λ. Examples include Poissondistributed arrivals (P

(A = k) = λ k
k! e -λ ), Bernoulli arrivals (P (A = 1) = λ and P (A = 0) = 1 -λ) as well as geometric arrivals (P

(A = k) = (1 -µ)µ k , µ = λ/(1 + λ)).
Our results do not depend on the specific distribution, however.

We call x n ∈ N the number of waiting customers, counted just after the arrivals at slot n. The admission decision of the controller takes place just after arriving customers have been taken into account. The set of decisions, or action space, is denoted with Q = {0, 1}, where q n ∈ Q is the number of customers admitted into service at slot n: 0 if no customer is admitted and 1 otherwise. We assume that the controller may choose q n = 1 even if x n = 0, which has of course no effect. The number of customers remaining in the buffer just after the decision is then y n = (x n -q n ) + , with x + = max(0, x).

During a slot, losses can occur because customers become impatient and leave. It is assumed that each customer has a constant probability α ∈ [0, 1] of leaving in each slot, independently from the past and from other customers. This is equivalent to assuming that the patience of each customer is geometrically distributed on N with parameter α. 2 For notational convenience, we introduce the stochastic operators I(y) and S(y) which count, respectively, the number of customers lost (impatient) and remaining (survivors), out of y present at the beginning of a slot. Conditioned on the value of y n = y, the number of losses during one slot, I(y), is a Binomial random variable with mean αy; likewise, S(y) is a Binomial random variable with mean αy, where α = 1 -α. This is a consequence of the independence and memoryless assumptions made on the impatience. Observe that for a given slot, I(y) and S(y) are correlated since I(y)+S(y) = y. This will not cause problems in the analysis.

With this notation, we can state the central representation of the dynamics of the system. The evolution of the state from slot n to slot n + 1 is given by the recurrence equation:

x n+1 = R(x n , q n ) := S (x n -q n ) + + A n+1 , (1)
whereas the number of customers lost in slot n is equal to I((x n -q n ) + ).

Stochastic Monotonicity Properties. We conclude by recalling useful properties of the stochastic operators we have introduced. From basic properties of the binomial distribution, it is possible to write the equality between distributions

S(x + 1) = d S(x) + B(1) , (2)
with B(1) a Bernoulli random variable of parameter α. The random variables in the right-hand side being independent. For a possible generalization based on this property, one can see the conclusion.

Recall the following notion of stochastic ordering of random variables, and the property of the Binomial family.

Definition 1 (Stochastic order [START_REF] Stoyan | Comparison Methods for Queues and Other Stochastic Models[END_REF]). We say that a random variable X is stochastically greater than a random variable Y (denoted by

X ≥ st Y ) if P(X ≤ t) ≤ P(Y ≤ t), or, equivalently, if Ew(X) ≥ Ew(Y ) for every nondecreasing function w. Proposition 2. For any x ≥ y ∈ N we have S(x) ≥ st S(y). If X ≥ st Y , then S(X) ≥ st S(Y ).

Elements of the Markov Decision Process

Transition probabilities

The dynamics of the controlled process are characterized by the probabilities to move in state z, given that the state is y and the action is q ∈ Q: P (z|(y, q)). Formally P (z|(y, q)) = P (x n+1 = z|x n = y, q n = q) .

(3)

These probabilities do not depend on n: the transition probabilities are homogeneous in time. Given the recurrence (1), and conditioning on the number of survivors, this can be expressed as:

P (z|(y, q)) = min(z,(y-q) + ) i=0 P S (y -q) + = i P A = z -i .

Rewards/Costs

The costs associated with decisions and transitions are the following. First, there is a setup cost which is incurred at the decision epoch when the controller chooses to admit one customer into service. If the choice is to keep the customer in the queue no cost is incurred. We denote by c B this setup cost. It is assumed that c B > 0. Second, there is a cost associated to each customer leaving the queue due to impatience. This cost, at slot n, is c L I(y n ), where c L is the cost of a single loss. Finally, there is an holding cost c H per remaining customer. We assume that it applies to all customers present after the service admission decision, so that the cost for slot n is c H y n .

In order to fit in the framework of [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF], we have to express the immediate cost (or negative reward) at each slot as a deterministic function of the current state and the current decision. Conditioned on the number of customers present x n = x and given that the decision is q n = q, the average cost due to losses (see Section 2.1)

is c L E(I(x -q) + ) = c L α(x -q) + .
It is therefore indeed possible to express the cost incurred by taking decision q when the state is x, as the function of (x, q):

c(x, q) = q c B + (c L α + c H ) (x -q) + = q c B + c C (x -q) + , (4)
where c C = αc L + c H is the per-capita cost for customers. Observe that this cost function is not bounded, unless c C = 0.

Decision policies

We call policy a sequence of decision rules π = (d 0 , d 1 , . . .), each decision rule mapping some information set to some action. While the most general set of policies is that of history-dependent randomized policies, Π HR , the classical results on discounted, infinite-horizon, time-homogeneous Markovian optimal control allow us to concentrate on Markov Deterministic Policies. Such policies are characterized by a single, deterministic decision rule which maps the current state to a decision. We denote with Π the set of such policies (denoted as D M D in [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF]). We consider a discounted cost criterion and the discount factor is denoted by θ. We make this choice in order to avoid the complexities associated with the average cost criterion. Nevertheless a brief explanation for the case θ → 1 can be seen in conclusion. Under each policy π, the evolution of the system generates a random sequence of states x n and decisions q n . We define the value function of policy π by the total expected discounted cost:

v π θ (x) = E π x ∞ n=0 θ n c(x n , q n ) ,
where x 0 = x. Our aim is to find the optimal policy π * ∈ Π HR such that

∀x ∈ N , v π * θ (x) = v * θ (x) = min π∈Π HR v π θ (x).
The following operators T , L and L d , acting on functions v, will be useful in the analysis:

(T v)(x, q) = c(x, q) + θ y∈N P (y|(x, q)) v(y) = c(x, q) + θ E [v (R(x, q))] , (5)
(L d v)(x) = (T v)(x, d(x)) . and (Lv)(x) = min d∈Π (L d v)(x) .
With this notation, the dynamic programming equation is v θ = Lv θ and finding the solution to this fixed point problem solves the dynamic programming problem.

Structural properties of the optimal policy

In this part we study the structural properties of value functions in order to get qualitative results on the optimal policy. Specifically, we prove that the optimal policy is of threshold type. The framework is that of property propagation through the Dynamic Programming operator. It consists in three steps: first exhibit some structural properties of the operator T v under special conditions on v (this implies some qualitative results on π * ). Then show that the properties of v are kept by the operator T v. At last, check that these properties are kept when passing to the limit. A structure theorem then allows to ensure that there exists an optimal policy and states, at the same time, that this optimal policy can be chosen in the set of structured policies.

For easier reference, we first recall the methodological framework and the results we will need from the literature. Next, we prove that the dynamic programming operator for our problem propagates monotonicity and convexity. Finally, we deduce the desired property for the optimal policy.

Structured policies

We say that a policy is a structured policy if it has a special form (for example increasing, decreasing...). Together with the notion of structured policies, comes a notion of structured value functions. Both notions are adapted to each other. Let V σ be the set of structured value functions and D σ the set of structured decision rules. A structured policy Π σ is a sequence of structured decision rules.

The following theorem indicates which properties have to be conserved (or propagated) by the dynamic programming operator. Two sets of properties are required in this theorem: properties ( 6)-( 8) are related with the existence of solutions under unboundedness of the cost function; conditions 0) to iii) are the structural conditions per se. Theorem 3 ([15], Theorem 6.11.3). Assume that the following properties hold: there exists a positive function on the state space, w, such that:

sup (x,q) |c(x, q)| w(x) < + ∞ , (6)
sup

(x,q) 1 w(x) y P(y|x, q)w(y) < + ∞ , (7)
and for every µ, 0 ≤ µ < 1, there exists η, 0 ≤ η < 1 and some integer J, such that, for every J-uple of Markov Deterministic decision rules π = (d 1 , . . . , d J ), and every x,

µ J y P π (y|x)w(y) ≤ ηw(x) , (8)
where P π denotes the J-step transition matrix under policy π. Let V w be the set of functions on the state space which have a finite w-weighted supremum norm (i.e. sup x |v(x)/w(x)| < +∞) and V σ ⊂ V w . Assume that: 0. for each v ∈ V w , there exists a deterministic Markov decision rule

d such that Lv = L d v. If, furthermore, i. v ∈ V σ implies T v ∈ V σ , ii. v ∈ V σ implies there exists a decision d such that d ∈ D σ ∩ arg min d L d v,
iii. V σ is a closed subset of the set of value functions by simple convergence.

Then, there exists an optimal stationary policy (d * ) ∞ in Π σ with d * ∈ arg min d L d v.

We introduce now the key submodularity property and its consequences. Definition 4 (Submodularity [START_REF] Glasserman | Monotone Structure in Discrete-Event Systems[END_REF]). A real-valued function g defined on two partially ordered sets X ×Q is called submodular (or subadditive) if it has monotone decreasing differences. That is, if it verifies the inequality g(x + , q + ) -g(x -, q + ) ≤ g(x + , q -) -g(x -, q -),

for any x + ≥ x -∈ X and any q + ≥ q -∈ Q.

Proposition 5 ([15], Lemma 4.7.6). Let g be a real valued function defined on N × {0, 1}. If the difference function x → g(x, 1) -g(x, 0) is nonincreasing, then the function g is submodular.

These properties allow to deduce a structural property of the optimal control Proposition 6 (Monotone optimal control [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF], Lemma 4.7.1). Let g(x, q) be a submodular function on two partially ordered sets such that, min x g(x, q) exists for any x. If g(x, q) is submodular then the control function q(x) = min{arg min q∈Q (g(x, q))} , is increasing i.e. x + ≥ x -yields q(x + ) ≥ q(x -).

Structural properties of the dynamic programming operator

In this part we establish structural results of the dynamic programming operator for our system: propagation of monotonicity, submodularity and convexity.

Lemma 7 (Propagation of monotonicity). Let ṽ be the function defined by ṽ(x) = min q T v(x, q) for any x ∈ N. Then ṽ is nondecreasing in

x if v is nondecreasing in x.
Proof. The definition of T v in (5) involves two terms given in Eqs. ( 4) and [START_REF] Altman | Handbook of Markov Decision Processes Methods and Applications, chapter Applications of Markov Decision Processes in Communication Networks : a survey[END_REF]. We show first that the lump costs c(x, q) are nondecreasing for a given decision q. Indeed, from Equation (4) the cost is either equal to (x -1)c C + c B or xc C which are nondecreasing in x.

From Proposition 2, it follows that S ((x + 1 -q) + ) ≥ st S ((x -q) + ). Therefore we have that R(x + 1, q) ≥ st R(x, q). Recall (Definition 1) that if X ≥ st Y , then Ew(X) ≥ Ew(Y ) for every nondecreasing function w. As a consequence, the function T v(x, q) is the sum of two increasing functions of x for every q. The minimum over q is therefore also increasing.

Lemma 8 (Submodularity). For any nondecreasing convex function v, the function T v(x, q) is submodular on N × Q.

Proof. We have the decomposition:

∆ q T v(x) = T v(x, 1) -T v(x, 0) = c(x, 1) -c(x, 0) + θ∆ q T v(x) , (9)
where:

∆ q T v(x) = y∈N P y|(x, 1) v(y) - y∈N P y|(x, 0) v(y) = Ev(S((x -1) + ) + A) -Ev(S(x) + A) . (10)
First of all, observe that the difference c(x, 1) -c(x, 0) = c B -c C does not depend on x ≥ 1. On the other hand, for x = 0, we simply have: ∆ q T v(0) = 0 and c(0, 1)-c(0, 0) = c B thus ∆ q T v(0) = c B .

We then prove the nonincreasingness of x → ∆ q T v(x) for any x > 0. In that case, we use the stochastic decomposition (2), written as S(x) = S(1) + S(x -1), in [START_REF] Koole | Queueing models of call centers: An introduction[END_REF] to get:

∆ q T v(x) = Ev(S(x -1) + A) -Ev(S(x -1) + S(1) + A) = a,s P(A = a, S(1) = s) (Ev(S(x -1) + a) -Ev(S(x -1) + s + a)) = - a,s P(A = a, S(1) = s) E [u a,s (S(x -1))] , (11)
where we have defined: u a,s (y) =v(y+s+a)-v(y+a). Since v is increasing and convex, the function u a,s (y) is nonnegative and increasing for all nonnegative values of a and s. The stochastic increasingness of the S(x) (Proposition 2), implies (see Definition 1) that Eu a,s (S(x)) ≥ Eu a,s (S(x -1)), for all x ≥ 1 and all s, a ≥ 0. This last inequality is conserved by convex combinations. As a result, the expression ( 11) is a nonincreasing function of x > 0. It is also negative, so that when x = 1:

∆ q T v(1) = c B -c C + θ∆ q T v(1) ≤ c B = ∆ q T v(0) .
The function is therefore nonincreasing at x = 0 as well. We conclude that ∆ q T v(x) = T v(x, 1) -T v(x, 0) is indeed nonincreasing in x and then, by Proposition 5, T v(x, q) is submodular.

Lemma 9 (Propagation of convexity). Let ṽ be the function defined by ṽ(x) = min q T v(x, q) for any x ∈ N. Then ṽ is nondecreasing convex in x if v is nondecreasing convex in x.

Proof. The nondecreasingness comes from Lemma 7. We just have to prove the convexity.

Assume then that v is nondecreasing convex. Define q * y = arg min q T v(x, q), and let ∆ x ṽ(y) be defined as ∆ x ṽ(y) =ṽ(y + 1) -ṽ(y) = T v(y + 1, q * y+1 ) -T v(y, q * y ). We shall prove that the function ∆ x ṽ(y) is nondecreasing, which is equivalent to the convexity of ṽ.

As proved in Lemma 8, the function T v(y, q) is submodular. As a consequence of Proposition 6, the function y → q * y is therefore nondecreasing. Henceforth, the couple (q * y+1 , q * y ) can take only one of the three values (0, 0), (1, 0) and (1, 1). These cases correspond to, respectively, y ≤ ȳ -2, y = ȳ -1 and y ≥ ȳ, where ȳ is the integer number, potentially infinite, such that ∆ q T v(ȳ -1) > 0 and ∆ q T v(ȳ) ≤ 0. Observe that ȳ ≥ 1 because ∆ q T v(0) = c B > 0.

The case y = ȳ -1 is the simplest: in that case ∆ x ṽ(ȳ -1) = c B . For y ≤ ȳ -2, since q y+1 = q y = 0, we have:

∆ x ṽ(y) = c C + θ [Ev(S(y + 1) + A) -Ev(S(y) + A)] . (12)
If on the other hand y ≥ ȳ, since q y+1 = q y = 1, we have:

∆ x ṽ(y) = c C + θ [Ev(S(y) + A) -Ev(S(y -1) + A)] . (13)
The same stochastic increasingness arguments as in the proof of Lemma 8 allow to conclude that ∆ x ṽ(y) is increasing in both cases, that is, for y ≤ ȳ -2 and y ≥ ȳ. There remains to show that ∆ x ṽ(ȳ -2) ≤ ∆ x ṽ(ȳ -1)(= c B ) ≤ ∆ x ṽ(ȳ). Using ( 9), ( 10) and ( 12), we conclude that:

c B -∆ x ṽ(ȳ -2) = ∆ q T v(ȳ -1) . Likewise ∆ x ṽ(ȳ) -c B = -∆ q T v(ȳ) .
By definition of ȳ, both these quantities are nonnegative. Therefore ∆ x ṽ(y) is nondecreasing and thus the convexity propagates.

Structural properties of the optimal policy

We present now deterministic policies which are called either threshold policies in [START_REF] Altman | Handbook of Markov Decision Processes Methods and Applications, chapter Applications of Markov Decision Processes in Communication Networks : a survey[END_REF] or control limit policies in [START_REF] Deb | Optimal control of batch service queues[END_REF].

One calls threshold policy a Markovian deterministic policy such that

q(x) = q 1 if x < ν q 2 if x ≥ ν
where q 1 and q 2 are in Q and ν is called the threshold. In other words, if the system is in a state under the threshold then it is optimal to perform q 1 and q 2 is optimal elsewhere.

Theorem 10. The optimal policy is increasing in x (it is a monotone control) and is a threshold policy.

Proof. We apply Theorem 3 with V σ the set of nondecreasing convex functions, and D σ the set of monotone controls.

Let us first check that the preliminary conditions ( 6)-( 8) are satisfied. We choose as weighing function: w(x) = C + c C x, for some constant C > 0 to be determined in the course of the proof. Such a function satisfies [START_REF] Glasserman | Monotone Structure in Discrete-Event Systems[END_REF] because the ratio in the right-hand side of ( 6) is an homographic and bounded function.

Firstly, we have, using the notation introduced earlier,

y P(y|(x, q))w(y) = E(w(A + S((x -q) + ))) = C + c C E(A + S((x -q) + )) = C + c C (λ + α((x -q) + )) ≤ C + c C λ + α(c C x) .
It follows that sup q y P(y|(x, q))w(y)/w(x) is also bounded by an homographic and bounded function of x.

Finally, consider any sequence of Markov decision rules d j . Since w is increasing, we always have: E(w(A + S((x -d j (x)) + ))) ≤ E(w(A + S(x))). Let us call R(x) = R(x, 0) and denote with R (n) the n-th iteration of this operator. It follows that

y P π (y|x, q)w(y) ≤ E(w( R (J) (x))) = C + c C E( R (J) (x)) = C + c C (λ + ᾱE( R (J-1) (x))) = C + c C λ 1 -α J 1 -α + c C α J x .
Assume first that α > 0. If one chooses the constant C = λc C /α, then:

y P π (y|x, q)w(y) ≤ C + c C λ 1 α + α J (c C x) = 2C + α J (c C x) .
Next, for any µ < 1, there exists some J such that 2µ J is less than 1. For this J and every sequence of J decision rules, and taking η ∈ (2µ J , 1)

µ J y P π (y|x, q)w(y) ≤ 2µ J C + µ J α J (c C x) ≤ ηw(x) .
Consider now the case α = 0. Then

y P π (y|x, q)w(y) ≤ C + c C λJ + c C x .
Whatever the constant C, for any µ < 1, there exists an integer J such that µ J (C + λc C J)/C < 1. It is therefore possible to find a constant η < 1 as above. Finally, Property [START_REF] Kocaga | Admission control for a multi-server queue with abandonment[END_REF] holds in all cases.

In order to apply Theorem 3, it is next required that condition 0) hold. Here, Theorem 6.2.10 of [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF] implies that this is the case, as a consequence of the finiteness of the action space.

We proceed to check that the three structural conditions of Theorem 3 are satisfied. Lemma 9 insures that the value function issued from operator T is still nondecreasing convex if the input value function is nondecreasing convex. Thus i) is checked. Moreover, Lemmas 7 and 8 combined with Proposition 6 prove that the optimal control is nondecreasing as soon as the value function is nondecreasing convex. This shows ii). At last, the point-wise convergence of a sequence of nondecreasing convex functions is convex, therefore iii) holds.

Therefore, there exists an optimal policy which is a monotone control. Given that the action space has two elements, this is actually a threshold policy.

As a corollary, we also obtain that the value function is nondecreasing and convex.

The optimal threshold

We are now interested by computing the threshold values accordingly the parameters values. This means determining the customer load of the system from which it becomes more efficient to serve customers than to do nothing. An infinite threshold means that it is never optimal to accept customers. The approach used here is to compute an expression for the value function of a general threshold policy, then use a sample path analysis (see e.g. [START_REF] Liu | Sample path methods in the control of queues[END_REF]) in order to establish the monotonicity of this value function.

Theorem 11. Let ψ be the number defined by

ψ = c B - c C 1 -αθ .
Then, i. If ψ > 0, the optimal threshold is ν = +∞.

ii. If ψ < 0, the optimal threshold is ν = 1.

iii. If ψ = 0, any threshold ν ≥ 1 gives the same value.

The proof needs a preliminary Lemma. Define first the operator R ν by

R ν (x) = A + S (x -1 x≥ν ) + , (14)
and denote with R

(n) ν the n-th iteration of the operator R ν .

Lemma 12. Let Φ ν (x, θ) be the function defined by

Φ ν (x, θ) = ∞ n=0 θ n P(R (n) ν (x) ≥ ν) .
Then the function Φ ν (x, θ) is positive, increasing with respect to x for every fixed ν and decreasing with respect to ν for fixed x.

5 Discussion and Extensions

Interpretations and Comparative Statics

An interpretation of Theorem 11 is as follows. Given the choice between serving immediately or never the first customer in line, the controller faces an immediate cost c B for service, and a future, discounted cost for letting the customer remain in the system until it gets impatient. This cost turns out to be c C /(1 -αθ). Assume that the controller chooses not to serve this customer. It has then no reason for serving any other customer because they are all symmetric, given the memoryless deadline distribution. At the next slot, for every customer present the same dilemma would occur between two average costs, still because of the Markovian nature of the impatience process. Instead, in a discounted case the cost of postponing an decision has to be taken into account. The monotonicity result of Lemma 8 show this cost has either a negligible long term cost (ν = +∞) or not (ν = 1). Therefore, the optimal decision can be made on a customer-per-customer basis. This leads to a policy where customers are served as soon as they arrive (ν = 1) or never (ν = +∞).

According to this interpretation, it is not too surprising that the optimal policy does not depend on λ, although the value function does. It may be for instance that the rate of arrivals is larger than the service capacity. If the impatience process is active (α > 0), the queue always remain stable, and average holding costs remain bounded over time. If α = 0, the queue may build up, and holding costs increase over time. However, the presence of the discount factor makes the value function finite.

Next, the value of ψ defined in Theorem 11 is: increasing with respect to c B , decreasing with respect to c L and c H ; the optimal threshold ν * varies in the same direction as ψ (from 1 to +∞), which is conform to intuition. It can be seen also that ψ and ν * are decreasing with respect to θ. Finally, ν * is increasing with respect to α if c L ≤ θc H /(1 -θ), and decreasing in the converse case.

The extreme cases for α also have a reasonable explanation. When α = 1, every customer not served in one slot leaves the system before the next slot. It is therefore optimal to serve one customer among the recently arrived ones (corresponding to a threshold of one) if the setup cost c B is smaller than the per-customer cost c C = c L +c H . This is consistent with Theorem 11 since ψ = c B -(c L +c H ) in this case. At the opposite, when α = 0, customers never leave spontaneously the system. There is no loss cost incurred and ψ = c B > c H /(1 -θ) in Theorem 11. If the holding cost is zero, the threshold is therefore infinite: it is optimal never to serve any customer. If we had allowed c B to be negative, the threshold would be equal to 1.

Methodological issues

It could be objected to the present paper that since the optimal policy is very simple (serve or no serve), there is probably a simpler way to prove it than to use the machinery of property propagation. This feeling is reinforced by the interpretations of the previous paragraph. We argue in this section that this criticism is true only to some extent: in our opinion, the direct proofs may not be substantially more compact, and they have less potential for generalization.

Two alternate proof techniques are candidate: direct verification and coupling.

Direct verification. It is indeed possible to prove Theorem 11 by computing the value function for the optimal policy (always serve if ψ < 0, never serve if ψ > 0) and check that they solve Bellman's equation Lv = v. Observe first that this approach still necessitates a proof that this equation has a unique solution: one still needs to check that conditions ( 6)-( 8) hold, as in the proof of Theorem 10.

Computing the candidate value function is what we have done in Section 4. Proving that it solves Bellman's equation turns out to be indeed simple in the case ψ > 0 with the function

V ∞ (x) = c C 1 -θα x + θE(A) 1 -θ .
For the case ψ(x) < 0, the value function has no such simple closed form, and proving that it solves Bellman's equation requires establishing additional monotonicity properties similar to Lemma 15 as well as convexity properties. In the end, the proof does not appear to be substantially shorter.

Coupling arguments. The simplicity of the decision rule suggests that simple comparison arguments should be sufficient. For instance, if the optimal policy is "always serve", show that not serving a customer is sub-optimal as compared to serving it. Such reasoning is usually made formal through coupling arguments: both trajectories are constructed on the same probability space.

The most natural coupling is perhaps the one we use in Appendix 7. With this coupling, it is not possible to show that serving one customer systematically results in a gain or a loss. This can be seen through a counterexample 13 and also through the fact that the criterion on ψ involves average costs, and not only instantaneous costs. Another reason is that we use a discounted cost, for which the cost of some action depends on the time at which it is taken. Interchange arguments are usually used in the context of average or total costs. Example 13. We assume that the parameters are such that c B < c C 1-ᾱθ (implying the optimality of the "always serve" policy) and such that c B > c H + c L . These assumptions are satisfied for a wide range of parameters since ᾱ and θ are smaller than one and since that c H + c L = c C + ᾱc L . We however show on a simple sample of a path that this is not better to serve the customer than to let it in the system.

Assume there is a set of x customers waiting. By coupling arguments let us assume that there is only one customer expected to leave the system at the next step and that this dedicated customer is this one for which a decision has to be taken. Using Eq. (5, the costs induced by the choice to admit the customer is c B + (x -1)c H + θE(v(x -1)) while the costs induced by the other choice is c L + xc H + θE(v(x -1)). The difference between these two costs is equal to c B -(c L + c H ) which is non negative by assumption. So, it would be better to let the customer in the system.

The coupling technique which corresponds directly to the interpretation of Section 5.1 consists in coupling residual impatience times of present customers in two trajectories corresponding to two distinct controls. This is possible a priori thanks to the memoryless property of the Geometric distribution. Using this technique requires the introduction of a formal apparatus, additional notation and a rigorous proof of the fact that relevant distributions are the same in the coupled systems (see e.g. [START_REF] Liu | Sample path methods in the control of queues[END_REF]).

We have therefore chosen not to pursue this line of proof.

Extensions

We discuss here some extensions of the present model for which the principal result is preserved. As we have mentioned in the introduction, we envision other natural extensions (multiple servers, finite capacity, several impatience classes, non-unit service) but those do not fit yet in the framework we have developed here. The extension of the results to the average cost criterion does not seem to be difficult, in the sense that letting θ = 1 in Theorem 11 does not cause problems: the value of ψ is just defined as c B -c L -c H /α, with an obvious interpretation. The needed increasingness property of Lemma 12 holds for the limit: lim θ→1 (1 -θ)Φ ν (x, θ), so that Tauberian arguments are likely to be applicable.

Finally, the results obtained here extend to the case where customers do not simply disappear due to impatience, but are replaced with a random number B of new customers, in the manner of Galton-Watson branching processes. In that situation, the parameter α in the cost function ( 4) is to be interpreted as P(B = 0). The parameter α is the branching factor EB and does not coincide anymore with (1 -α). The stochastic increasingness property (2) still holds, with B(1) ≡ B. The preliminary conditions for Theorem 3 (see the proof of Theorem 10) hold as long as α = EB < 1, which corresponds to the stability of the process without service. The coupling argument of Lemma 15 can be extended as well to a branching process.

Conclusion

In this paper we have shown that the optimal control of service in a single queue with impatience is a threshold policy and we give the closed form of the value of this threshold. If the framework used could seem to be usual, its application here requires some additional concepts which do not appear in previous work. For example, here the monotonicity of the control requires a convex value function contrarily to the usual cases where only monotonicity of the value function is required (see [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF]). This is due to the random departures due to impatience, which completely modify the dynamical behavior.

Because of this, the extension of the problem to the case where the server may serve more than one customer at a time, does not work in a straightforward manner. This may be seen on the simulation below, where for a case of batch of size larger than one, the dynamical operator does not have the submodular property of Lemma 8. The trajectory comparison result in Lemma 15 does not hold either.

Example 14. Consider the model presented in Section 2, except that the server can serve batches of size up to B = 5. The evolution of the system (1) then becomes x n+1 = R(x n , q n ) := S (x n -q n B) + + A n+1 , where q n ∈ {0, 1} as before. The parameters are θ = 0.9, c B = 1, c L = 0.5, c H = 0, α = 0.2, λ = 1 and the distribution of arrivals is Poisson. The sequence T v(x, 1) -T v(x, 0) is non monotone. Indeed its values obtained by simulations (taking a size of the queue of 100) for respectively x from 0 to 8 are: 1.0, 0.709, 0.438, 0.192, -0.029, -0.249, -0.203, -0.197 and -0.224. If the function T v were submodular, this sequence would be nonincreasing (Proposition 5); this is not the case.

On the other hand, no experimental evidence has contradicted, so far, the possibility that the optimal control still be of threshold type. Similar issues are addressed in [START_REF] Örmeci | Structural results on a batch acceptance problem for capacitated queues[END_REF] for the dual problem of admission control of batches. The challenge of further research on the topic will therefore be to find the appropriate properties that can be propagated by the dynamic programming operator in this case. This is why such a work is a first step basis. First, by showing that structural properties can be found even though it is not the submodularity for more complex cases. And equally by showing that the propagation of properties of the value function is necessary but not sufficient. Indeed, notions of "K-convexity" used in contexts which look similar (see [START_REF] Altman | On submodular value functions and complex dynamic programming[END_REF] and [START_REF] Papadaki | Exploiting structure in adaptative dynamic programming algorithms for a stochastic batch service problem[END_REF]) do not work, because they would result in a submodular function T v(x, q), which is contradicted by Example 1 above.

RR n°6881

As usual in this type of models, customers arriving during a slot are supposed to be notified to the system only at the beginning of the next slot.

This is the equivalent for discrete time to the exponential distribution of deadlines in continuous time models.

The Proof of Lemma 12 is postponed in appendix.

Proof of Theorem 11. When the policy is a threshold policy with threshold ν, the evolution of the system is:

ν (x 0 ). Then, according to Eq. ( 14), we have:

since x -1 x≥ν is always nonnegative, for every x ≥ 0 and ν ≥ 1.

Next, if the state is x, the cost incurred by the control policy becomes:

since the acceptance of a customer occurs only when the queue is not empty, implying that the threshold is strictly greater than 0. Hence, if X is a random variable, we have the expectation:

Using these properties, the value function, when the threshold policy is with threshold ν, at the initial state x can be computed as follows:

With, using Equation [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF],

Consequently, we get

The dependence on ν is concentrated in the function Φ ν , but, by Lemma 12, we know that Φ ν (x, θ) is positive, increasing with respect to x for every fixed ν and decreasing with respect to ν for fixed x. Since we want for all x, arg min ν V ν (x), if ψ > 0 then the optimal value of ν = ∞ while if ψ < 0 the optimal value is ν = 1. If ψ = 0, V ν does not depend on ν and all values give the same result.

Appendix: Proof of Lemma 12

The proof of Lemma 12 requires some preliminary results and notations. Hence, we denote with π ν the threshold policy with threshold ν. Let us denote O (n) ν the set of customers present in the system at slot n under policy π ν . This set is evaluated at the beginning of the nth slot just before the decision. Customers are leaving this set due to either losses or service. We shall compare the sequences

ν+1 . We assume that the two stochastic systems are coupled through their arrival sequences, and the impatience of each customer. In other words, it is assumed that, at each slot, the same amount of customers arrive and also that the customers which are present simultaneously in both queues will leave simultaneously because of impatience.

It may however happen that at some slot, one customer is expected to leave under one of the policies, whereas it has been already serviced under the other policy and is not present in the corresponding queue. In this case nothing else occurs for this customer.

Lemma 15. For every trajectory, we have

where j n is the customer of smaller index in O . Otherwise, we have

Our claim is therefore proved.

We can now prove the lemma.

Proof of Lemma 12. It is sufficient to prove that each function P(R (n) ν (x) ≥ ν) enjoys the claimed properties. These functions are obviously positive. They are increasing with respect to x because the operator R ν is stochastically increasing: R ν (x + 1) ≥ st R ν (x). There remains to prove the non-increasingness with respect to ν for every fixed x. This amounts to show that

Observe that R


Nicolas Bonichon

Cyril Gavoille
email: gavoille@labri.fr.

Nicolas Hanusse
email: hanusse@labri.fr.

David Ilcinkas
email: ilcinkas@labri.fr.

Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces

Keywords: Delaunay triangulation, theta-graph, orthogonal surface, spanner, realizability

Θ k -graphs are geometric graphs that appear in the context of graph navigation. The shortest-path metric of these graphs is known to approximate the Euclidean complete graph up to a factor depending on the cone number k and the dimension of the space.

TD-Delaunay graphs, a.k.a. triangular-distance Delaunay triangulations introduced by Chew, have been shown to be plane 2-spanners of the 2D Euclidean complete graph, i.e., the distance in the TD-Delaunay graph between any two points is no more than twice the distance in the plane.

Orthogonal surfaces are geometric objects defined from independent sets of points of the Euclidean space. Orthogonal surfaces are well studied in combinatorics (orders, integer programming) and in algebra. From orthogonal surfaces, geometric graphs, called geodesic embeddings can be built.

In this paper, we introduce a specific subgraph of the Θ6-graph defined in the 2D Euclidean space, namely the half-Θ6-graph, composed of the even-cone edges of the Θ6-graph. Our main contribution is to show that these graphs are exactly the TD-Delaunay graphs, and are strongly connected to the geodesic embeddings of orthogonal surfaces of coplanar points in the 3D Euclidean space.

Using these new bridges between these three fields, we establish:

• Every Θ6-graph is the union of two spanning TD-Delaunay graphs. In particular, Θ6graphs are 2-spanners of the Euclidean graph, and the bound of 2 on the stretch factor is best possible. It was not known that Θ6-graphs are t-spanners for some constant t, and Θ7-graphs were only known to be t-spanners for t ≈ 7.562.

• Every plane triangulation is TD-Delaunay realizable, i.e., every combinatorial plane graph for which all its interior faces are triangles is the TD-Delaunay graph of some point set in the plane. Such realizability property does not hold for classical Delaunay triangulations.

Introduction

A geometric graph is a weighted graph whose vertex set is a set of points of R d , and whose edge set consists in line segments joining two vertices. The weight of any edge is the Euclidean distance (L 2 -norm) between its endpoints. The Euclidean complete graph is the complete geometric graph, in which all pairs of distinct vertices are connected by an edge.

Although geometric graphs are in theory specific weighted graphs, they naturally model many practical problems and in various fields of Computer Science, from Networking to Computational Geometry. Delaunay triangulations, Yao graphs, theta-graphs, β-skeleton graphs, Nearest-Neighborhood graphs, Gabriel graphs are just some of them [START_REF] Goodman | Handbook of discrete and computational geometry[END_REF]. A companion concept of the geometric graphs is the graph spanner. A t-spanner of a graph G is a spanning subgraph H such that for each pair u, v of vertices the distance in H between u and v is at most t times the distance in G between u and v. The value t is called stretch factor of the spanner.

Spanners have been independently introduced in Computational Geometry by Chew [START_REF] Chew | There is a planar graph almost as good as the complete graph[END_REF][START_REF] Chew | There are planar graphs almost as good as the complete graph[END_REF] for the complete Euclidean graph, and in the fields of Networking and Distributed Computing by Peleg and Ulman [START_REF] Peleg | An optimal synchronizer for the hypercube[END_REF][START_REF] Peleg | An optimal synchornizer for the hypercube[END_REF] for arbitrary graphs. Literature in connection with spanners is vast and applications are numerous. We refer to Peleg's book [START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF], and Narasimhan and Smid's book [START_REF] Narasimhan | Geometric Spanner Networks[END_REF] for comprehensive introduction to the topic.

Orthogonal surfaces

With a point set M of R d it is possible to associate other geometric objects. Assuming that M consists only of pairwise incomparable1 points, the orthogonal surface of M is the geometric boundary of the set of points of R d greater to at least one point of M (see Fig. 2 for d = 3).

Orthogonal surfaces are rich mathematical objects with connections to various fields, including order dimension, integer programming, and monomial ideals. Schnyder woods and orthogonal surfaces of coplanar points of R 3 have being established by Miller and Felsner et al. [Mil02,[START_REF] Felsner | Schnyder woods and orthogonal surfaces[END_REF]. As a side effect, they gave an intuitive proof of the Brightwell-Trotter Theorem which is an extension to multigraphs of Schnyder's characterization of planar graphs in term of dimension of their incidence order [START_REF] Schnyder | Planar graphs and poset dimension[END_REF].

The geodesic embedding of a point set S ⊂ R2 is a geometric graph with vertex set S. To define its edges, one consider a specific embedding φ : S → R 3 such that the points of φ(S) are coplanar (see Section 2). There is an edge between the points p, q ∈ S if the join point φ(p) ∨ φ(q) belongs to the orthogonal surface of φ(S), the join point being defined as the point with maximum coordinates between φ(p) and φ(q) in each dimension.

Delaunay-graphs

In his seminal paper, Chew [START_REF] Chew | There is a planar graph almost as good as the complete graph[END_REF] has constructed plane spanners of the 2D Euclidean graph, namely planar subgraphs whose stretch factor is at most √ 10 ≈ 3.162. His construction is based on the L 1 -Delaunay graph, i.e., the dual of the Voronoi diagram for the Manhattan distance (L 1 -norm). He conjectured that L 2 -Delaunay graphs, i.e., classical Delaunay triangulations, are t-spanners for some constant t. This conjecture has been proved by [START_REF] Dobkin | Delaunay graphs are almost as good as complete graphs[END_REF], and the current best bounds on the stretch factor t of L 2 -Delaunay graphs are 1.584 < t < 2.419, proved respectively by [BDL + 09] and [START_REF] Keil | Classes of graphs which approximate the complete euclidean graph[END_REF]. Determining the exact stretch factor of this important class of geometric graphs is a challenging and open question. We refer to the recent survey [START_REF] Bose | On plane geometric spanners: a survey and open problems[END_REF].

More generally, for any given convex set Γ in the plane 2 , one can define the Γ-Delaunay graphs as the dual of the Voronoi diagram of a set of points with respect to the convex distance function defined by Γ. Bose et al. [START_REF] Bose | On the stretch factor of convex delaunay graphs[END_REF] have shown that Γ-Delaunay graphs are plane t-spanners for some stretch factor t depending on the shape of Γ.

A natural question, widely open, is to determine whether L 2 -Delaunay graphs are the "best" plane spanners in term of stretch factor. Chew has proved in [START_REF] Chew | There is a planar graph almost as good as the complete graph[END_REF] that no plane t-spanner can exist if t < √ 2 ≈ 1.414, because of the square, a regular 4-gon. This lower bound has been slightly improved by [START_REF] Mulzner | Minimum dilation triangulations for the regular n-gon[END_REF] with a regular 21-gon, showing that t > 1.416. On the upper bound side, Chew introduced in [Che89] the triangular distance-Delaunay graphs, TD-Delaunay graphs for short, whose convex distance function is defined from an equilateral triangle. He proved that TD-Delaunay graphs are plane 2-spanners. The stretch 2 is optimal with respect to the triangular distance because of some 3-gons.

Delaunay realizability

Searching for the "best" plane spanner should be done, a priori, in the set of all planar graphs. Indeed, there is no advantage to limit the search to any restricted subclass, excepted maybe to plane triangulations. By plane triangulation we mean a combinatorial plane graph in which all its interior faces are triangles. However, there are notorious plane triangulations that cannot be obtained from any L 2 -Delaunay graphs, e.g., a K 4 for which a degree-3 vertex is added in each of its three interior faces [START_REF] Michael | Toughness and delaunay triangulations[END_REF][START_REF] Lenhart | Drawable and forbidden minimum weight triangulations[END_REF]. This leads to the question of realizability of plane triangulations by L 2 -Delaunay graphs, and more generally by Γ-Delaunay graphs for a convex distance function Γ. More formally, a plane triangulation G is Γ-Delaunay realizable if there exists a point set S such that the Γ-Delaunay graph of S is isomorphic to G.

Every triangulation of any polygon, i.e., every maximal outerplane graph, can be realized by a L 2 -Delaunay graph [START_REF] Michael | Toughness and delaunay triangulations[END_REF]. Based on 3D hyperbolic geometry, Hodgson et al. [START_REF] Hodgson | A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere[END_REF] gave a combinatorial characterization of the graphs that are L 2 -Delaunay realizable, leading to a polynomial-time recognition algorithm by the use of integer programming. The algorithm has been simplified later in [START_REF] Hiroshima | Another proof of polynomial-time recognizability of delaunay graphs[END_REF][START_REF] Lillis | On the efficiency of a local iterative algorithm to compute delaunay realizations[END_REF]. Other connections between toughness, polyhedra of inscribable type, and L 2 -Delaunay graphs have been developed in [START_REF] Dillencourt | Graph-theoretical conditions for inscribability and delaunay realizability[END_REF]. For arbitrary convex distance function D, the D-Delaunay realizability has not yet been studied.

Theta-graphs

Theta-graphs [START_REF] Clarkson | Approximation algorithms for shortest path motion planning[END_REF][START_REF] Keil | Approximating the complete euclidean graph[END_REF] and Yao graphs [START_REF] Andrew | On constructing minimum spanning trees in k-dimensional spaces and related problems[END_REF] are very popular geometric graphs that appear in the context of navigating graphs. Adjacency is defined as follows: the space around each point p is decomposed into k 2 regular cones, each with apex p, and a point q = p of a given cone C is linked to p if, from p, q is the "nearest" point in C. When the points are in general positions, the out-degree is at most k and form a non-planar graph whenever k > 6.

Theta-graphs and Yao graphs differ in the way the nearest neighbor is defined. We focus on the 2D Euclidean space, so that each cone forms an angle of Θ k = 2π/k. For Yao graphs (Y k -graphs for short), the nearest neighbor of p in the cone C is simply a point q = p minimizing the L 2 -distance between p and q. Whereas for theta-graphs (Θ k -graphs for short), the nearest neighbor of p is the point whose orthogonal projection onto the bisector of C minimizes the L 2 -distance.

Both graphs are known to be efficient spanners. The stretch factor of Θ k -graphs and Y k -graphs, proved respectively in [START_REF] Ruppert | Approximating the d-dimensional complete Euclidean graph[END_REF] and in [START_REF] Andrew | On constructing minimum spanning trees in k-dimensional spaces and related problems[END_REF], is at most 1/(1 -2 sin(π/k)) for every k > 6. Very little is known for k 6. For instance, it is known that Y 4 -graphs are connected [START_REF] Fischer | Geometric searching in walkthrough animations with weak spanners in real time[END_REF], but it is only conjectured that Y 4 -graphs are t-spanners for some constant t (see [DMP09, O'R09] for recent developments). For k = 7, and according to the current upper bound, we observe that the stretch of these graphs is larger than 7.562, and the stretch drops under 2 only from k 13.

Our main result relies on a specific subgraph of the Θ k -graph, namely the half-Θ k -graph, taking only half the edges, those belonging to non consecutive cones in the counter-clockwise order (see Section 2 for more a formal definition). For even k, every Θ k -graph is the union of two spanning half-Θ k -graphs.

Our results

Our main contribution is an unexpected connection between TD-Delaunay graphs, orthogonal surfaces, and theta-graphs. We stress that these objects come from rather different domains and can lead to new results. We show that (see Section 3 for a more precise statement):

For every point set S ⊂ R 2 in general position, the TD-Delaunay graph of S, the geodesic embedding of S, and the half-Θ 6 -graph of S are equal.

Half-Θ 6 -graph turns out to be a key ingredient of our result. This unification result implies that each of these objects can directly inherit of all the known properties from the others. In particular, we exhibit two important corollaries:

1. Every Θ 6 -graph is the union of two spanning TD-Delaunay graphs.

In particular, Θ 6 -graphs are 2-spanners of the 2D Euclidean graph, because they contain a TD-Delaunay graph as spanning subgraph, which is a 2-spanner from [START_REF] Chew | There are planar graphs almost as good as the complete graph[END_REF]. Since the bound of 2 is optimal, we have therefore determined the stretch factor of Θ 6 -graphs. Up to now, Θ 6 -graphs were not known to be t-spanners for any constant t, and the best known bound on the stretch factor for Θ 7 -graphs was larger than 7.562. Before this current paper, only Θ k -graphs for k 13 were known to be 2-spanners (see the previous best general upper bound [START_REF] Ruppert | Approximating the d-dimensional complete Euclidean graph[END_REF]).

The other important consequence is:

Every plane triangulation is TD-Delaunay realizable.

We also show that the plane triangulation of K 4 is not L 1 -Delaunay realizable, so that, to the best of our knowledge, the equilateral triangle is the only regular convex distance function D that is known to have the property that every plane triangulation is D-Delaunay realizable.

The paper is organized as follows. In Section 2 we precisely define all the objects we need, and in Section 3 we prove our main result. The corollaries are proved in Section 4.

Definitions

Half-Θ 6 -graph

A cone is the region in the plane between two rays that emanate from the same point, its apex. For each cone C, let ℓ C be the bisector ray of C, and for each point p, let C p = {x + p : x ∈ C}.

Let us consider the rays obtained by a counter-clockwise rotation of the positive x-axis by angles of 2iπ/k with integer i. Each pair of successive rays 2(i -1)π/k and 2iπ/k defines a cone, denoted by A i , whose apex is the origin.

Let A k = {A 1 , . . . , A k }. The directed Θ k -graph of a point set S ⊂ R 2 , denoted by -→ Θ k (S), is defined as follows: (1) vertex set of -→ Θ k (S) is S; and (2) (p, r) is an arc of -→ Θ k (S) if and only if there is a cone A i ∈ A k such that r ∈ A p
i \ {p} whose orthogonal projection onto ℓ p C is the closest to p. We now introduce a new graph, called half-Θ k -graph, defined as follows:

Definition 1 The directed half-Θ k -graph of a point set S ⊂ R 2 , denoted by 1 2 -→ Θ k (S)
, is the digraph induced by all the arcs (p, r) of -→ Θ k (S) such that r ∈ A p i for some even number i.

Whenever k ≡ 2 (mod 4), we denote by C i the cone A 2i , and by C i the opposite cone of C i , i.e., C i = A 2i+k/2 mod 6 (observe that 2i + k/2 is odd). An arc (p, r) such that r ∈ C p i is said to be colored i. In this paper, we focus on the half-Θ 6 -graph. So, in counter-clockwise order starting from the positive x-axis, the six cones of A 6 are encountered in the order The set of points S is said to be degenerated if there exist two points p and q in S such that both (p, q) and (q, p) are arcs of 1 2 -→ Θ k (S). The set S is said to be non-degenerated otherwise.

ℓ C 3 C 2 C 3 C 1 ℓ C 2 C 2 C 1 C 3 ℓ C 1 (b)
C 2 , C 1 , C 3 , C 2 , C 1 , C 3 (see Fig. 1(a)).

Geodesic embeddings

Let P be a plane equipped with the standard basis (e x , e y ), and let S be a finite set of points in the plane P.

The following definitions are extracted from [START_REF] Miller | Planar graphs as minimal resolutions of trivariate monomial ideals[END_REF]. Let (e 1 , e 2 , e 3 ) be the standard basis of R 3 . The plane P is now embedded in P ′ ⊂ R 3 where P ′ is the plane containing the origin of R 3 with basis (e ′

x , e ′ y ) where e ′ x = (0, -1/ √ 2, 1/ √ 2) and e ′ y = ( 2/3, -1/ √ 6, -1/ √ 6). Observe that e 1 + e 2 + e 3 is a normal vector 3 of P ′ . Any point p = (p x , p y ) ∈ R 2 is mapped to p ′ ∈ P ′ with p ′ = p x e ′

x + p y e ′ y . Consider the dominance order on R 3 : p q if and only if p i q i for each i = 1, 2, 3. Note that any two different points of P ′ are incomparable. The filter generated by a set of points S of P is the set

S = α ∈ R 3 : α v for some v ∈ S .
The boundary S S of S is the coplanar orthogonal surface generated by S. Notice that in [START_REF] Miller | Planar graphs as minimal resolutions of trivariate monomial ideals[END_REF][START_REF] Felsner | Schnyder woods and orthogonal surfaces[END_REF], the authors also consider orthogonal surfaces, a more general case where elements of S are pairwise incomparable but not necessarily in the same plane of normal vector e 1 +e 2 +e 3 .

Fig. 2 shows an example of a coplanar orthogonal surface. We denote by p∨q the point (max{p 1 , q 1 }, max{p 2 , q 2 }, max{p 3 , q 3 }). If p, q ∈ S and p∨q ∈ S S , then S S contains the union of the two line segments joining p and q to p ∨ q. These lines are called elbow geodesics of S S . The orthogonal arc of p ∈ S in direction of the standard vector e i is the piece of ray p + λe i , λ 0, which follows a crease of S S . If p ∨ q is equal to p + λe i , for some λ 0, we say that it is an elbow of type i. The corresponding elbow geodesic is also said to be of type i. Observe that p ∨ q shares two coordinates with at least one (and perhaps both) of p and q. We say that a geodesic elbow is uni-directed if its corresponding elbow p ∨ q shares two of its coordinates either with p or with q (but not with both).

An orthogonal surface S S is uni-directed if all the geodesic elbows are uni-directed.

Definition 2 Let S be a set of points on P such that the orthogonal surface S S is uni-directed. The geodesic embedding of S is the directed graph --→ Geo(S) defined as follows:

• vertices of --→ Geo(S) are the points of S.

• there is an arc from p to q colored i if and only if p ∨ q is an elbow of type i.

TD-Delaunay triangulation

We recall here the definition of TD-Delaunay graphs introduced in [Che89].

Let T (resp. T ) be the equilateral triangle of size length 1 whose barycenter is the origin and one of its vertices is on the positive (resp. negative) y-axis . A homothet of T is obtained by scaling T with respect to the origin, followed by a translation: p + λT = {p + λz : z ∈ T }. The triangular distance between two points p and q is defined as follows:

d T (p, q) = min {λ : λ 0 and q ∈ p + λT } Notice that in general d T (p, q) = d T (q, p).
Let S be a set of points in the plane P. For each p ∈ S, we define the TD-Voronoi cell of p as: We say that a set of points S is non-ambiguous if the intersection of any two TD-Voronoi cells of S is of null area4 . Definition 3 Let S be a non-ambiguous set of points of P. The TD-Delaunay graph of S, denoted by TDDel(S), is defined as follows:

V T (p) = {x ∈ P : for all q ∈ S, d T (p, x) d T (q, x)} .
• vertex set of TDDel(S) is S; and 3 Unification of the concepts

• (p, q) is an edge of TDDel(S) if and only if V T (p) ∩ V T (q) = ∅.

Preliminaries

Given two points p and q ∈ C p i , we denote by T i (p, q) the set of points of P in C p i \ {p} whose orthogonal projection onto ℓ C p i is strictly closer to p than the orthogonal projection onto ℓ C p i of q. Note that the boundary of T i (p, q) is an equilateral triangle. The interior of T i (p, q) is denoted by T • i (p, q). Differently speaking, T • i (p, q) is the set of points T i (p, q) deprived of the points lying on the axes of the cone C p i .

Lemma 1 Let S be a set of points in the plane P, and let p and q be two distinct points in this set. There is an arc (p, q) colored i in 1 2 -→ Θ 6 (S) if and only if q ∈ C p i and T i (p, q) ∩ S = ∅.

Proof. This follows directly from the definition of 1 2 -→ Θ 6 (S) (see Def. 1) and of T i (p, q).

Lemma 2 Let S be a set of points in the plane P, and let p and q be two distinct points in this set. p ∨ q is an elbow of type i if and only if q ∈ C p i and T • i (p, q) ∩ S = ∅.

Proof. Let S be a set of points in the plane P, and let p and q be two distinct points in this set. Without loss of generality, assume that p is the point with coordinates (0, 0, 0) and let (q 1 , q 2 , q 3 ) be the coordinates of q. Note that the cone C i p can be described as the set of points r = (r 1 , r 2 , r 3 ) such that r i 0 and r j 0 for all j = i. Moreover, the point p is the only point r of C i p such that r i = 0, and the interior of the cone C i p is exactly the set of points r such that r i > 0 and r j < 0 for all j = i. These remarks are illustrated in Fig. 4. We now prove the lemma for i = 1. The cases i = 2 and i = 3 can be treated similarly.

By definition, p ∨ q is an elbow of type 1 if and only if (1) the point p ∨ q shares the two coordinates of index 2 and 3 with the point p, and (2) p ∨ q lies on the orthogonal surface S S .

The point p ∨ q shares the two coordinates of index 2 and 3 with the point p if and only if q 1 > 0 and q 2 , q 3 0, and thus, according to the previous remarks, if and only if q ∈ C p 1 . Assume now that q ∈ C p 1 , that is p ∨ q = (q 1 , 0, 0). The point p ∨ q lies on the orthogonal surface S S if and only if it lies on the boundary of the filter generated by S, that is, if and only if there does not exist any point r ∈ S such that r 1 < q 1 and r 2 , r 3 < 0. Since the set of points r such that r 1 < q 1 and r 2 , r 3 < 0 is exactly T • i (p, q), we have that p ∨ q lies on S S if and only if

T • i (p, q) ∩ S = ∅.
This concludes the proof of the lemma. Lemma 3 Let S be a set of points in the plane P, and let p and q be two distinct points in this set. The Voronoi cells V T (p) and V T (q) share at least a point if and only if there exists i ∈ {1, 2, 3} such that q ∈ C p i and

T • i (p, q) ∩ S = ∅, or p ∈ C q i and T • i (q, p) ∩ S = ∅.
Proof. Let S be a set of points of P, and let p and q be two distinct points in this set. Before proving the two parts of the equivalence, let us make the following remark. A point r ∈ P belongs to both Voronoi cells V T (p) and V T (q) if and only if there exists some λ > 0 such that both p and q lies on the boundary of T ′ = r + λ T and such that the interior of T ′ does not contain any point of S. Indeed the boundary of T ′ consists exactly of the set of points s such that d T (s, r) = λ and the interior of T ′ consists exactly of the set of points s such that d T (s, r) < λ.

(⇐=) Assume that there exists i ∈ {1, 2, 3} such that q ∈ C p i and T • i (p, q) ∩ S = ∅, or p ∈ C q i and T • i (q, p) ∩ S = ∅. Without loss of generality, we have q ∈ C p 1 and T • i (p, q) ∩ S = ∅. From the previous remark, the center r of T • i (p, q) belongs to both Voronoi cells V T (p) and V T (q). (=⇒) Assume that the Voronoi cells V T (p) and V T (q) share at least a point r. It implies that there exists some λ > 0 such that both p and q lie on the boundary of T ′ = r + λ T and such that the interior of T ′ does not contain any point of S.

Assume first that p and q lies on the same edge of the triangle T ′ . Let T ′′ be the positive homothet of T ′ (and thus of T ) having both p and q as vertices. The interior of T ′′ is empty because it is included in the interior of T ′ . Noticing that that there exists i ∈ {1, 2, 3} such that T • i (p, q) is exactly the interior of T ′′ allows to conclude the proof in this case. Assume now that p and q lie on different edges of the triangle T ′ . Let s be the common point of these edges, and let T ′′ be the triangle obtained by a homothety of T ′ of center s and of minimum ratio such that both p and q still lie on the boundary of T ′′ . Again there exists i ∈ {1, 2, 3} such that T • i (p, q) or T • i (q, p) is exactly the interior of T ′′ , and this interior is empty. This concludes the proof of this lemma.

Equivalences

We first prove the links existing between the different notions of "general position" corresponding to the three objects into consideration.

Theorem 1 Let S be a set of points in the plane P.

1. S is non-degenerated if and only if S S is uni-directed.

If S is non-degenerated, then S is non-ambiguous.

Proof. Given two points p and q, let Ti (p, q) be the closure of T i (p, q) deprived of the three vertices of the triangle. We will prove that the three different notions of "general position" are more or less equivalent to the fact that there do not exist two points p and q in S and i ∈ {1, 2, 3} such that p and q are two of the vertices of Ti (p, q) and Ti (p, q) ∩ S = ∅.

Let S be a set of points in the plane P. S is degenerated if and only if there exist two points p and q in S such that both (p, q) and (q, p) are arcs of the directed graph 1 2 -→ Θ k (S). Using Lemma 1, (p, q) and (q, p) are arcs of 1 2 -→ Θ k (S) of respective color i and j if and only if Ti (p, q) = Tj (q, p) and Ti (p, q) ∩ S = ∅. To summarize, S is non-degenerated if and only if there does not exist two points p and q in S and i ∈ {1, 2, 3} such that p and q are two of the vertices of Ti (p, q) and Ti (p, q) ∩ S = ∅.

Let S be a set of points in the plane P. The orthogonal surface S S is not uni-directed if and only if there exist two points p and q in S such that p and q are as close as possible (using norm L 2 ) and such that p∨q is an elbow of type i and q ∨p is an elbow of type j (j = i). Using Lemma 2, p ∨ q is an elbow of type i and q ∨ p is an elbow of type j if and only if

T • i (p, q) = T • j (q, p) and T • i (p, q) ∩ S = ∅.
Taking into account that p and q are as close as possible, we have that S S is not uni-directed if and only if there exist two points p and q in S and i ∈ {1, 2, 3} such that p and q are two of the vertices of Ti (p, q) and Ti (p, q) ∩ S = ∅. This proves Point 1 of the Lemma.

Let S be a non-degenerated set of points in the plane P. Assume, for the purpose of contradiction, that S is ambiguous. It means that there exist two points p and q in S such that the intersection of the two TD-Voronoi cells V T (p) and V T (q) is of non-null area. This implies that the angle between e x and the line going through p and q is congruent to 0 modulo π/3. Indeed, if it is not the case, then for any λ > 0, the intersection of the two triangles p + λT and q + λT consists of at most two points, which implies that the intersection of V T (p) and V T (q) is necessarily of null area. Without loss of generality, assume that p = (-√ 3, 1) and q = ( √ 3, 1). See Fig. 3(b) for an illustration. As shown at the beginning of the proof, the fact that S is non-degenerated implies that there exists a point r ∈ S in T3 (p, q). By choosing p and q (with the stated properties) such that the distance between them is minimum (using L 2 -norm), we can ensure that r does not lie on the segment with extremities p and q. Hence the triangular distance from r to any node in the part of the plane below the two lines (o, u) and (o, v) where o = (0, 0) is smaller than the triangular distance from p or q. Since this part of the plane contains the interior of the intersection V T (p) ∩ V T (q), this intersection must be of null area. This contradiction with the fact that S is ambiguous concludes the proof.

We are now ready to prove our main equivalence theorem.

Theorem 2 Let S be a non-degenerated set of points in the plane P. Let Geo(S), resp. 1 2 Θ 6 (S), be the underlying undirected uncolored graph of --→ Geo(S), resp.

1 2 -→ Θ 6 (S). 1 2 Θ 6 (S) = Geo(S) = TDDel(S)
.

Moreover, we have

--→ Geo(S) = 1 2 -→ Θ 6 (S) .
Proof. Let S be a non-degenerated set of points in the plane P. From Theorem 1, all the graphs appearing in the statement of the theorem are well defined. From Lemma 2 and Lemma 3, we immediately have Geo(S) = TDDel(S). It remains to show --→ Geo(S) = 1 2 -→ Θ 6 (S) to conclude the proof.

Let p and q be any two distinct points in the non-degenerated set S such that p ∨ q is an elbow of type i. From Lemma 2, we thus have q ∈ C p i . Assume, for the purpose of contradiction, that

T • i (p, q) ∩ S = ∅ but T i (p, q) ∩ S = ∅.
Let r be any point of S in T i (p, q) \ T • i (p, q). We have that r ∈ C p i and T • i (p, r) ∩ S = ∅ but we also have p ∈ C r j and T • j (r, p) ∩ S = ∅, for some j = i. Thus, from Lemma 2, p ∨ r is an elbow of type i and an elbow of type j, which contradicts the fact that S is non-degenerated, i.e., that S S is uni-directed. Thanks to this proof by contradiction, we have that two distinct points p and q in a non-degenerated set S satisfy that p ∨ q is an elbow of type i if and only if q ∈ C p i and T i (p, q) ∩ S = ∅. From Definition 2 and Lemma 1, we have that there is an arc (p, q) colored i in 1 2 -→ Θ 6 (S) if and only if there is an arc (p, q) colored i in --→ Geo(S). This concludes the proof of the theorem.

Applications

Spanner

In [START_REF] Chew | There are planar graphs almost as good as the complete graph[END_REF] it is shown that TD-Delaunay triangulations are 2-spanners. From Theorem 2 we directly get the following corollary:

Corollary 1 Every half-Θ 6 -graph (and also Θ 6 -graph) is a 2-spanner. Moreover the edges of Θ 6 -graph can be partitioned into two planar graphs.

We observe that the bound of 2 is best possible stretch for half-Θ 6 -graphs. Indeed, the half-Θ 6graph of some 3-gons (the apex of a quasi-equilateral triangle) has stretch arbitrarily close to 2.

Delaunay realizability

Using face counting algorithm introduced by Schnyder [Sch89], Felsner and Zickfeld [FZ08, Theorem 10] showed that for every plane triangulation G, a point set S such that Geo(S) = G can be computed in linear time5 . Using the equivalence between geodesic embeddings and TD-Delaunay triangulations (Theorem 2) we directly get the following result (see Section 1.3 for the definition of realizability):

Corollary 2 Every plane triangulation is TD-Delaunay realizable.

This raises the following natural question: is there another distance function Γ such that every triangulation is Γ-Delaunay realizable? The first natural distance to be considered is the L 1 -norm. The next theorem shows that not all triangulations are L 1 -Delaunay realizable.

Theorem 3 The plane triangulation of K 4 is not L 1 -Delaunay realizable.

In order to prove Theorem 3 we first present a technical lemma: Lemma 4 Let S be a point set. Let u 1 , u 2 and u 3 be three points of S. Let ∆ 1 and ∆ 2 be the lines going through u 1 of slope π/4 mod π. These two lines split the plane around u 1 into four quater-planes. If u 2 and u 3 belong to the interior of two non-consecutive quater-planes, there is no edge (u 2 , u 3 ) in the L 1 -Delaunay graph of S.

Proof. Let u 1 , u 2 and u 3 be three points satisfying the hypothesis of the lemma. Assume without loss of generality that u 1 = (0, 0) and that u 2 (resp. u 3 ) belongs to the quater-plane containing the negative part (resp. positive part) of x-axis.

If S contains only the 3 considered vertices, one can easily check that the L 1 -Voronoi cell of u 2 (resp. u 3 ) is included in the half-plane of strictly negative (resp. strictly positive) abscissa (see Fig. 5). Remark that adding new points to S can not extend the Voronoi cells of u 2 and u 3 . Hence for any S, the Voronoi cells of u 2 and u 3 lie on disjoint part of the plane. Hence there is no edge between u 2 and u 3 in the L 1 -Delaunay graph of S.

This concludes the proof of this lemma.

Proof of Theorem 3. Let us prove by contradiction that the plane triangulation of K 4 can not be realized as a L 1 -Delaunay graph. Let S = {u 1 , u 2 , u 3 , u 4 } such that its L 1 -Delaunay graph is isomorphic to the plane triangulation of K 4 . From Lemma 4 applied 3 times around u 1 considering the edges (u 2 , u 3 ), (u 3 , u 4 ) and (u 4 , u 2 ) we have that u 2 , u 3 , u 4 must all lie in at most two consecutive quater-planes. Applying this argument around each vertex shows that the four vertices are in convex position.

For convenience, assume that the vertices of the convex polygon defined by S are labeled u 1 , u 2 , u 3 and u 4 in the clockwise order. Hence the edges (u 1 , u 3 ) and (u 2 , u 4 ) cross each other in the L 1 -Delanay graph. The resulting L 1 -Delaunay graph corresponds to K 4 but is not a planar representation of K 4 because of the edge crossing. It turns out that the plane triangulation of K 4 can not be realized as L 1 -Delanay graph.

To conclude on realizability, let us mention, that there are graphs that are realizable for a certain distance function and not for another and vice versa. For instance, Theorem 3 shows that K 4 is not L 1 -Delaunay realizable but it is L 2 -Delaunay realizable (see the four points p 1 , p 2 , p 3 , p 5 of Fig. 1(b) realizing K 4 ). On the other hand, Fig. 6 shows that there also exist graphs that are L 1 -Delaunay realizable but not L 2 -Delaunay realizable [Dil90, Fig. 4].

Figure 6: A triangulation that is L 1 -Delaunay realizable but not L 2 -Delaunay realizable.

Final remarks

A Voronoi diagram is sometime interpreted as a view from the top of a collection of cones whose apices lie on a plane and whose axes are oriented downward (see for example [HKL + 99]). Coplanar orthogonal surfaces are the exact generalisation of this idea for TD-Voronoi diagrams: the only difference lies on the shape of the base of the cones: circular (L 2 -norm), square (L 1 -and L ∞ -norm) or triangular (triangular distance). Hence the TD-Voronoi cell of a point p of S is exactly the orthogonal projection on P of the points of S S dominated by p (see figures 2 and 3).

Among various generalizations of Voronoi diagram, Additively Weighted Voronoi Diagram has been widely studied (see for example [START_REF] Lee | Generalization of voronoi diagrams in the plane[END_REF][START_REF] Menelaos | Dynamic additively weighted voronoi diagrams in 2d[END_REF][START_REF] Bose | Spanners of additively weighted point sets[END_REF]). In such a diagram, the point set is replaced by a set of weighted points S = {(p 1 , w 1 ), . . . , (p n , w n )}. The distance between an element (p i , w i ) of S and point x of the plane P is d AW ((p i , w i ), x) = d(p i , x) -w i . The AW-Vonoroi cell of a weighted point (p i , w i ) ∈ S is naturally defined as follows:

V AW (p i , w i ) = {x ∈ P : ∀(p j , q j ) ∈ S, i = j, d AW ((p i , w i ), x) d AW ((p j , w j ), x)} .

An AW-Voronoi diagram can be interpreted as a view from the top of a collection of cones where the altitude of the apex of a cone is the weight of the corresponding element of S.

In our context we can define Additively Weighted Triangular Distance Voronoi Diagram (or simply AWTD-Voronoi diagram) using the following notion of distance: d AW T D ((p i , w i ), x) = d T (p i , x)-w i . From the previous remarks, one can see orthogonal surfaces (not necessary coplanar) as AWTD-Voronoi diagrams.

The Yao graph [START_REF] Andrew | On constructing minimum spanning trees in k-dimensional spaces and related problems[END_REF] is very similar to the Θ-graph: in each cone of apex p, the selected neighbor of p is the nearest one in the cone instead of being the one with the nearest projection on ℓ C . Half-Y 6 -graphs can be defined as we did for half-Θ 6 -graphs considering only 3 of the six cones. Unfortunately, half-Y 6 -graphs do not have as nice structural properties. For instance, a half-Y 6 -graph is not planar in general.

Algorithms that compute Θ-graphs, geodesic embeddings and TD-Delaunay triangulations have been respectively proposed in [NS07, FZ08, CD85]. It appears that the 3 proposed algorithms run in O(n log n) and are all essentially based on the "plane-sweep" algorithm.

In a forthcoming paper, the main result is used to build planar bounded-degree spanner.

Figure 1 :

 1 Figure 1: (a) Illustration of notations for half-Θ 6 -graphs.(b) An example of a directed half-Θ 6graph.

  Fig. 1(b) shows an example of a directed half-Θ 6 -graph on 8 points.

Figure 2 :

 2 Figure 2: A coplanar orthogonal surface with its geodesic embedding.

Fig. 3

 3 Fig. 3(a) shows an example of set of TD-Voronoi cells, also called TD-Voronoi diagram. Observe that the intersection of two TD-Voronoi cells may have a positive area. For instance, consider the following set S = u = (-√ 3, 1), v = ( √ 3, 1) (see Fig. 3(b)). The intersection V T (u) ∩ V T (v) contains the part of the plane below the two lines (o, u) and (o, v) where o = (0, 0).We say that a set of points S is non-ambiguous if the intersection of any two TD-Voronoi cells of S is of null area 4 .

Figure 3 :

 3 Figure 3: (a) TD-Voronoi diagram. (b) λ 1 < λ 2 < λ 3 stand for three triangular distances. Set {u, v} is an ambiguous point set, however {u, v, w} is non-ambiguous.

Figure 4 :

 4 Figure 4: Partition of the plane P according to the sign of the coordinates of a point r = (r 1 , r 2 , r 3 ) in P.

Figure 5 :

 5 Figure 5: Impossible configuration for K 4 .

A point v is greater than u if, in for each dimension i, the ith v's coordinate is greater than the ith u's coordinate.

To be more precise, Γ must be a compact and convex set with non-empty interior that contains its origin.

For ambiguous set of points S, it is possible to have a partition of the plane by the interior of Voronoi cells plus the union of all boundaries, by ordering the elements of S to break ties. See for example[START_REF] Bose | On the stretch factor of convex delaunay graphs[END_REF].

Note that that this result holds also for 3-connected plane maps, but in this case the orthogonal surface is not uni-directed.

Supported by the ANR-project "ALADDIN", and the équipe-projet INRIA "CÉPAGE".

† Member of the "Institut Universitaire de France".