Esters of polyhydric alcohols, also known as polyol esters, find a variety of uses on a large scale in industry, for example as plasticizers or lubricants. The selection of suitable starting materials allows the physical properties, for example boiling point or viscosity, to be controlled, and the chemical properties, such as hydrolysis resistance or stability to oxidative degradation, to be taken into account. Polyol esters can also be tailored to the solution of specific performance problems. Detailed overviews of the use of polyol esters can be found, for example, in Ullmann's Encyclopaedia of Industrial Chemistry, 5th edition, 1985, VCH Verlagsgesellschaft, Vol. A1, pages 305-319; 1990, Vol. A15, pages 438-440, or in Kirk Othmer, Encyclopaedia of Chemical Technology, 3rd edition, John Wiley & Sons, 1978, Vol. 1, pages 778-787; 1981, Vol. 14, pages 496-498.
The use of polyol esters as lubricants is of great industrial significance, and they are used particularly for those fields of use in which mineral oil-based lubricants meet the requirements made only incompletely. Polyol esters are used especially as turbine engine and instrument oils. Polyol esters for lubricant applications are based frequently on 1,3-propanediol, 1,3-butanediol, 1,4-butanediol, 1,2-hexanediol, 1,6-hexanediol, neopentyl glycol, trimethylolpropane, pentaerythritol, 2,2,4-trimethylpentane-1,3-diol, glycerol or 3(4),8(9)-dihydroxymethyltricyclo[5.2.1.02,6]decane, also known as TCD alcohol DM, as the alcohol component.
Polyol esters are also used to a considerable degree as plasticizers. Plasticizers find a variety of uses in plastics, coating materials, sealing materials and rubber articles. They interact physically with high molecular weight thermoplastic substances, without reacting chemically, preferably by virtue of their swelling and dissolution capacity. This forms a homogeneous system, the thermoplastic range of which is shifted to lower temperatures compared to the original polymers, one result being that the mechanical properties thereof are optimized, for example deformation capacity, elasticity and strength are increased, and hardness is reduced.
In order to open up the widest possible fields of use to plasticizers, they must fulfil a series of criteria. They should ideally be odorless, colorless, and light-, cold- and heat-resistant. Moreover, it is expected that they are insensitive to water, comparatively nonflammable and not very volatile, and are not harmful to health. Furthermore, the production of the plasticizers should be simple and, in order to meet ecological requirements, avoid waste substances, such as by-products which cannot be utilized further and wastewaters comprising pollutants.
A specific class of polyol esters (they are referred to as G esters for short) contains diols or ether diols as the alcohol component, for example ethylene glycol, diethylene glycol, triethylene glycol, tetraethylene glycol, 1,2-propylene glycol or higher propylene glycols. They can be prepared in different ways. In addition to the reaction of alcohol and acid, optionally in the presence of acidic catalysts, further processes are employed in practice to obtain G esters, including the reaction of diol with acid halide, the transesterification of a carboxylic ester with a diol, and the addition of ethylene oxide onto carboxylic acids (ethoxylation). In industrial manufacture, only the direct reaction of diol and carboxylic acid and the ethoxylation of carboxylic acids have become established as production processes, preference usually being given to the esterification of diol and acid. This is because this process can be performed with no particular complexity in conventional chemical apparatus, and it affords chemically homogeneous products. Compared to this, ethoxylation requires extensive and costly technical equipment. Ethylene oxide is a very reactive chemical substance. It can polymerize explosively and forms explosive mixtures with air within very wide mixing ranges. Ethylene oxide irritates the eyes and respiratory pathways, leads to chemical burns and to liver and kidney damage, and is carcinogenic. The handling thereof therefore entails extensive safety measures. Moreover, scrupulous cleanliness of storage apparatus and reaction apparatus has to be ensured, in order to rule out the formation of undesired impurities as a result of side reactions of the ethylene oxide with extraneous substances. Finally, the reaction with ethylene oxide is not very selective, since it leads to mixtures of compounds of different chain length.
The direct esterification of alcohols with carboxylic acids is one of the basic operations in organic chemistry. In order to increase the reaction rate, the conversion is typically performed in the presence of catalysts. The use of one of the reactants in excess and/or the removal of the water formed in the course of the reaction ensures that the equilibrium is shifted in accordance with the law of mass action to the side of the reaction product, i.e. of the ester, which means that high yields are achieved.
Comprehensive information regarding the preparation of esters of polyhydric alcohols, also including esters of ethylene glycols and fatty acids, and regarding the properties of selected representatives of these compound classes can be found in Goldsmith, Polyhydric Alcohol Esters of Fatty Acids, Chem. Rev. 33, 257 ff. (1943). For example, esters of diethylene glycol, of triethylene glycol and of polyethylene glycols are prepared at temperatures of 130 to 230° C. over reaction times of 2.5 to 8 hours. To remove the water of reaction, carbon dioxide is used. Suitable catalysts mentioned for the esterification of polyhydric alcohols are inorganic acids, acidic salts, organic sulphonic acids, acetyl chloride, metals or amphoteric metal oxides. The water of reaction is removed with the aid of an entraining agent, for example toluene or xylene, or by introducing inert gases such as carbon dioxide or nitrogen.
The production and the properties of fatty acid esters of the polyethylene glycols are discussed by Johnson (edit.), Fatty Acids in Industry (1989) Chapter 9, Polyoxyethylene Esters of Fatty Acids, and a series of preparative details are given. Higher diester concentrations are achieved by the increase in the molar ratio of carboxylic acid to glycol. Suitable measures for removing the water of reaction are azeotropic distillation in the presence of a water-immiscible solvent, heating while passing through an inert gas, or performing the reaction under reduced pressure in the presence of a desiccant. When the addition of catalysts is dispensed with, longer reaction times and higher reaction temperatures are required. Both reaction conditions can be made milder by the use of catalysts. In addition to sulphuric acid, organic acids such as p-toluenesulphonic acid and cation exchangers of the polystyrene type are the preferred catalysts. The use of metal powders, such as tin or iron, is also described. According to the teaching from U.S. Pat. No. 2,628,249, color problems in the case of catalysis with sulphuric acid or sulphonic acids can be alleviated when working in the presence of activated carbon.
One procedure in which esters of diethylene glycol and of triethylene glycol and of caprylic acid are prepared without addition of catalyst is known from U.S. Pat. No. 2,469,446. The esterification temperature is in the range from 270 to 275° C. and the water of reaction is driven out by means of a carbon dioxide stream.
In the reaction regime in which the addition of a catalyst is dispensed with, a molar excess of the particular carboxylic acid is generally employed, which, owing to its acidity, also acts as a catalyst.
For the removal of the water of reaction formed in the formation of ester from the polyol and the carboxylic acids, various processes are known. For example, the water of reaction formed is distilled out of the reaction vessel together with the excess carboxylic acid and passed into a downstream phase separator in which carboxylic acid and water separate according to their solubility properties. In some cases, the carboxylic acid used also forms an azeotrope with water under the reaction conditions, and is capable of removing the water of reaction as an entraining agent. Other methods employed include azeotropic distillation in the presence of an added water-immiscible solvent, heating of the reaction mixture while passing through an inert gas, the reaction of the polyol and carboxylic acid starting materials under reduced pressure or in the presence of a desiccant. Especially the removal of water by azeotropic distillation has been found to be useful for the establishment of the equilibrium in the preparation of polyol esters. According to the procedure known from DE 199 40 991 A1, the water-immiscible solvent which acts as an entraining agent and must have a boiling point of less than 112° C. is added to the reaction mixture only on attainment of a temperature of at least 140° C.
In the industrial process, the mixture of water and carboxylic acid removed is separated in a phase separator into the organic and aqueous phases, the aqueous phase is discharged and the carboxylic acid is recycled back into the esterification reaction. For the workup of the crude ester, for example, U.S. Pat. No. 5,324,853 A1 proposes removing excess carboxylic acid by means of passage of nitrogen or steam, adding an adsorbent, neutralizing residual organic acid with a base, and filtering off solids obtained. The residual amounts of acid present in the filtrate are removed with the passage of steam or nitrogen with simultaneous application of a reduced pressure and recycled back into the esterification reaction. Solids obtained in the vacuum treatment are removed in a final fine filtration. One task of the adsorbent added, for example activated carbon, is to improve the color of the polyol ester.
According to the procedure known from U.S. Pat. No. 2,469,446 A1, the crude ester obtained after removal of the water of reaction and of excess, unconverted starting materials, for example carboxylic acid, is first treated with an alkaline reagent, for example with an aqueous sodium carbonate or sodium hydroxide solution, in order to remove last residues of acidic constituents. After washing with water, and treatment with bleaching earth and activated carbon, the last traces of odorous substances can be removed by applying reduced pressure at elevated temperature. In some cases, the treatment with bleaching agents and activated carbon has to be repeated more than once in order to produce polyol esters with satisfactory color properties.
Measures for improving the color of crude esters, such as oxidation, for example with hydrogen peroxide, or the adsorption of activated carbon, are known from the general prior art, for example from H. Suter, Phthalsäureanhydrid and seine Verwendung [Phthalic anhydride and use thereof], Dr. Dietrich Steinkopf Verlag, Darmstadt 1972. To improve the color of ester compounds based on polyols, WO 94/18153 A1 proposes a subsequent treatment with an aqueous hydrogen peroxide solution.
In addition, the prior art also discusses the action of ozone or ozone-containing gases on esters for color lightening. According to GB 783,463, esters of dicarboxylic acids, especially those based on oxo alcohols, are treated with ozone-containing air or ozone-containing oxygen below 100° C. This is followed by washing with an aqueous alkali metal hydroxide solution and then washing with water. This is followed by drying, for example by adding a desiccant or by heating under reduced pressure and subsequent filtration. The process steps otherwise customary in the workup of crude ester mixtures, such as treatment with activated carbon as an adsorbent or steam treatment to remove residual alcohol traces, may also follow the ozone treatment. According to the teaching of GB 813,867, the action of ozone is followed by treatment with a reducing agent, for example by washing with an aqueous solution comprising an alkali metal sulphite or by hydrogenation over a metal catalyst. There follow the process steps customary for the workup of crude esters. The measure of treatment with a reducing agent allows the peroxide content in the ester to be lower. According to U.S. Pat. No. 3,031,491 A1 too, the ozone treatment is followed by contacting of the crude esters with a reducing agent, which can reduce the peroxide content in the crude ester. According to the teaching of DE 27 29 627 A1, the ozone treatment is performed on carboxylic esters at a temperature of 15 to 90° C. with ozonized air, the ozone concentration being adjusted to a content of 5 to 50 mg/l. The ozone treatment is then followed by neutralization with an aqueous alkali metal hydroxide solution and washing with water. The action of direct steam under reduced pressure removes volatile alcohol and water traces. Subsequently, the product is contacted with an adsorbent and finally filtered.
Owing to the quality criteria described at the outset for polyol esters, the process steps in the esterification stage with removal of the water of reaction and in the workup of the crude ester are very important process features, since the adjustment of these process steps influences the sensory and optical properties of the end products to a significant degree. More particularly, high demands are placed on the color properties, such as low color number and high color stability, of the polyol esters. The structure of the starting materials, of the polyhydric alcohols and of the acids, is, in contrast, crucial for the mechanical and thermal properties of the polymer materials plasticized with the polyol esters and influences the hydrolysis and oxidation stability of lubricants.
The treatment with an adsorbent, for example activated carbon, high-surface area polysilicic acids, such as silica gels (silica xerogels), kieselguhr, high-surface area aluminium oxides and aluminium oxide hydrates, or mineral materials such as clays or carbonates, during the workup of the crude polyol ester to improve the color is a conventional process, but it requires additional filtration steps which mean a considerable level of complexity in a process performed industrially. Valuable product likewise remains adhering in the filter device and on the adsorbent, such that valuable product is lost in an additional filtration step.
Treatment with oxidizing agents, such as with hydrogen peroxide, ozone or with ozone-containing gases to lighten the color can also be found to be problematic since it can result in formation of organic peroxides during the treatment of the polyol esters. Traces of peroxides reduce the ester quality and the performance properties of the plasticized polymer products and of the lubricants produced on the basis of polyol esters. Peroxide traces also impair the storage performance of the polyol esters, and an increase in the peroxide number is observed during storage in spite of exclusion of oxidizing agents such as air. To reduce the peroxide number, the prior art proposes an additional treatment with a reducing agent. Although this process is capable of reducing the peroxide number, such an operation means an additional working step in which the reducing agent has to be provided and removed again after use thereof.


Q:

Spring Integration : How to add wadl(Restful service for JSON) contract to expose restful services like wsdl file

I want to expose project specific services as restful services(for JSON http request/response) that i exposed earlier for SOAP Request/Response type. Earlier we configured the static wsdl entries for SOAP using the
web-services:static-wsdl id="MyWsdl" location="/WEB-INF/xsd/MyWsdl.wsdl"/>
in the spring configuration files.
I need advice to know that Do we have ways to include my wadl contract files as we did for wsdl with the spring integration project or best way to expose my restful JSON service for the client.

A:

You can simply serve it up as a static resource from the WAR. See this question/answer for howto.


---
abstract: |
    We are given a finite set of $n$ points (*guards*) $G$ in the plane ${\mathbb{R}}^2$ and an angle $0\le\Theta\le2\pi$. A $\Theta$-cone is a cone with apex angle $\Theta$. We call a $\Theta$-cone *empty (with respect to $G$)* if it does not contain any point of $G$. A point $p\in{\mathbb{R}}^2$ is called *$\Theta$-guarded* if every $\Theta$-cone with its apex located at $p$ is non-empty. Furthermore, the set of all $\Theta$-guarded points is called the *$\Theta$-guarded region*, or the $\Theta$-region for short.

    We present several results on this topic. The main contribution of our work is to describe the $\Theta$-region with $O(\frac{n}{\Theta})$ circular arcs, and we give an algorithm to compute it. We prove a tight $O(n)$ worst-case bound on the complexity of the $\Theta$-region for $\Theta\ge\frac{\pi}{2}.$ In case $\Theta$ is bounded from below by a positive constant, we prove an almost linear bound $O(n^{1+\varepsilon})$ for any $\varepsilon>0$ on the complexity. Moreover, we show that there is a sequence of inputs such that the asymptotic bound on the complexity of the $\Theta$-region is $\Omega(n^2)$. In addition we point out gaps in the proofs of a recent publication that claims an $O(n)$ bound on the complexity for any constant angle $\Theta.$

    $\Theta$-guarded region, unoriented $\Theta$-maxima, convex hull generalization, good $\Theta$-illumination, $\alpha$-embracing contour.
author:
- Domagoj Matijević
- Ralf Osbild
title: 'Finding the $\Theta$-Guarded Region'
---

Introduction {#s:intro}
============

Illumination and guarding problems have been a popular topic of study in mathematics and computer science for several decades. One instance in this class of problems is the classical one posed by Victor Klee [@orourke87]: *How many guards are necessary, and how many are sufficient to patrol the paintings and works of art in an art gallery with $n$ walls?* While this particular problem has been solved shortly after by Chvatal [@ch75] proving a tight $\lfloor \frac{n}{3}\rfloor$ bound, many other variants in this problem class have appeared in the literature, see e.g. [@u-agip-00] for a general survey on the topic.

In this paper we consider a guarding problem with a fixed number of guards which have fixed positions in the plane. We concentrate on the mathematical description, the complexity, and the computation of the guarded area.

The model is as follows: We are given a finite set of points (*guards*) $G$ in the plane ${\mathbb{R}}^2$. A $\Theta$-cone is a cone with apex angle $\Theta$. We call a $\Theta$-cone *empty (with respect to $G$)*, if it does not contain any point of $G$ in its interior. A point $p\in{\mathbb{R}}^2$ is called *$\Theta$-guarded (with respect to $G$)*, if every $\Theta$-cone with apex located at $p$ is non-empty. The set of all $\Theta$-guarded points is called the *$\Theta$-guarded region*, or the $\Theta$-region for short. We consider $\Theta$-cones as open sets, hence the $\Theta$-region is an open set, too. The rationale behind this model is that a point is well-guarded only if it is guarded from all sides.

Previous Work
-------------

For a given set $G$ of $n$ points in the plane, Avis et al. [@avis] were the first to introduce the notion of *unoriented $\Theta$-maxima.* They say that some point $g\in G$ is a $\Theta$-maxima if there exists an empty $\Theta$-cone with apex at $g$. Hence a point $g$ is $\Theta$-maxima if it is not $\Theta$-guarded with respect to $G.$ They present an $O(\frac{n}{\Theta}\log n)$ algorithm for computing the unoriented $\Theta$-maximum of the set $G,$ or to put it in other words, an algorithm to query each point in $G$ if it is $\Theta$-guarded or not. A slight variation of their algorithm can actually query any finite point-set $P$ in $O(\frac{n+|P|}{\Theta}\log (n+|P|))$ time as we show in Lemma \[lm:avis\]. They further show that the unoriented $\frac{\pi}{2}$-maxima can be computed in $O(n)$ expected time.

Abellanas et al. [@ABM07] extent the guarding model (there it is called *good $\Theta$-illumination*) by a range $r$, i.e., a guard $g\in G$ can only guard points inside the circle of radius $r$ that is centered at $g$. Beneath other results they show how to check if a query point $p$ is $\Theta$-guarded in $O(n)$ time and output the necessary range and guards as witnesses.

Over years several generalizations of the standard convex hull of a point set have been proposed, like the $\alpha$-hull [@eks83], the $k$-th iterated hull [@c85], and the related concept of the $k$-hull ($k$-depth contour) [@csy87].

Our contribution {#our-contribution .unnumbered}
----------------

After some general observations, we describe the structure of the boundary of the $\Theta$-region for different values of $\Theta$ in Section \[s:general\]. There we also give an easy and efficient $O(n\log n)$ time algorithm to compute the boundary in case $\Theta\geq \pi.$ In the main part of the paper we concentrate on the case $\Theta<\pi$, since for these angles the problem becomes much more involved and the boundary of the $\Theta$-region more complex to understand. In Section \[s:boundary\] we show that the boundary of the $\Theta$-region is contained in an arrangement of circular arcs. In Section \[s:upperbounds\] we bound this set of arcs by $O(\frac{n}{\Theta})$. Note that in our work $\Theta$ and $n$ are independent parameters. In particular, asymptotic bounds are stated in $n$ and $\frac{1}{\Theta}.$ For $\Theta\ge \frac{\pi}{2}$ we prove that the complexity of the $\Theta$-region is $O(n)$. If $\Theta>\delta$ for a positive constant $\delta>0$, we show that the complexity is $O(n^{1+\varepsilon}),$ for any $\varepsilon>0.$ In Section \[s:lowerbound\] we give a generic example for a $\Theta$-region with complexity $\Omega(n^2)$ where the angle $\Theta$ is of order $\frac{1}{n}.$ In Section \[s:algorithm\] we give an algorithm to compute the $\Theta$-region in $O(n^{\frac{3}{2}+\xi}/\Theta + \mu \log n)$ time, for any $\xi>0$, where $\mu$ denotes the complexity of the arrangement of the $O(\frac{n}{\Theta})$ arcs. Our algorithm is based on the Partitioning Theorem [@Matousek] and on the computation of an arrangement of circular arcs.

#### Remark:

Besides our work there is an independent and very recent publication of Abellanas et al. [@ACM08]. There the complexity of the $\Theta$-region (called the $\alpha$-embracing contour) is claimed to be [linear]{} for [all]{} constant $\Theta$, and an algorithm that runs in $O(n^2\log n)$ time and $O(n^2)$ space is proposed. For constant $\Theta < \frac{\pi}{2}$ our $O(n^{1+\varepsilon})$ bound on the complexity of the $\Theta$-region is weaker than the claimed $O(n)$ bound. However, we believe that the main results in [@ACM08] are not correct, and we will point out two technical mistakes in the Appendix.

Remark on Plotted Pictures {#s:pictures}
--------------------------

The computer generated pictures are based on the value of the continuous function $f:{\mathbb{R}}^2\setminus G\to(0,2\pi]$ where $f(p)=\max\,\{\Theta: \exists\, \textrm{empty $\Theta$-cone with apex $p$} \}.$ The left picture of Figure \[fig:not\_connected\] and the two rightmost pictures in Figure \[fig:squared1\] are generated by plotting a grid point shaded, iff $f$ has a value below the threshold $\Theta$. In the right picture of Figure \[fig:not\_connected\] we have mapped different intervals of function values in $[0,\pi]$ to different gray scale values to visualize isolines (along the boundary of the gray scale value) of $f$ in this example. Although these pictures visualize only function values at grid points, one can rely on the pictures, since we deal with cones of a certain angle and not with arbitrarily thin stripes that could somehow pass between grid points.

The Shape of the $\Theta$-Guarded Region {#s:general}
========================================

We start with some observations. A point $p\in{\mathbb{R}}^2$ does not belong to the $\Theta$-region, if there is an empty $\Theta$-cone with apex $p$. Hence, no point inside an empty cone can belong to the region, and hence, the region can not contain holes. A point $p$ lies on the boundary of a $\Theta$-region, if the closure[^1] of each $\Theta$-cone with apex $p$ is non-empty, and there is at least one empty (open) $\Theta$-cone with apex at $p.$ The example in Figure \[fig:not\_connected\] shows that the $\Theta$-region is not necessarily connected for $0<\Theta<\pi$. The shape of the $\Theta$-region is invariant under translation, rotation, and scaling of $G.$

![An example with $|G|=50.$ The $\Theta$-region is not necessarily connected for $0<\Theta<\pi$ (left). The isolines of function $f$ show how components of the $\Theta$-region disconnect for decreasing $\Theta$ in this example (right).[]{data-label="fig:not_connected"}](fig/two_plots){width=".95\columnwidth"}

The shapes of all $\Theta$-regions can be grouped according to $\Theta$. The boundary of the $\pi$-region is just the *convex hull* ${\mathit{CH}}(G)$, because the intersection of all half-planes containing $G$ (convex hull) is the same as removing every half-plane from ${\mathbb{R}}^2$ that does not contain any point of $G$ ($\pi$-region). However, for $0<\Theta<\pi$, empty (convex) $\Theta$-cones can enter the convex hull through the edges, while for $\pi<\Theta<2\pi$ the apexes of empty (concave) $\Theta$-cones do not even have to touch the convex hull (see Figure \[fig:shaperegions\]).

![For $\Theta<\pi$ (resp. $\Theta>\pi$) the region lies inside (outside) the convex hull ${\mathit{CH}}(G)$ and the bounding arcs are bend inside (outside) the region.[]{data-label="fig:shaperegions"}](fig/shape_regions){width=".8\columnwidth"}

Therefore, the $\Theta$-region is connected, if $\Theta\ge\pi$. Trivially, the $2 \pi$-region is the plane ${\mathbb{R}}^2$ and the $0$-region is the empty set.

Before we discuss the $\Theta$-region for $0<\Theta<\pi$ in Sections \[s:boundary\]–\[s:algorithm\], we discuss the simpler case $\pi<\Theta<2\pi$ below. Throughout the paper we use the property about *inscribed angles:* *Given a circular arc $C_{l,r}$ from $l$ to $r$, then $\angle lpr = \angle lqr$ holds for all $p,q\in C_{l,r}$.* We write $C_{l,r}^\alpha$ if the inscribed angle is $\alpha$. The arc end points are always given in counterclockwise order.

Finding the $\Theta$-Guarded Region for $\Theta > \pi$ {#s:larger}
------------------------------------------------------

As already discussed (see Figure \[fig:shaperegions\]), for $\Theta>\pi$ every point in the convex hull interior of $G$ is $\Theta$-guarded. Intuitively, the boundary of the $\Theta$-region is drawn by the apex of an empty $\Theta$-cone which is rotated around the convex hull ${\mathit{CH}}(G)$ such that its rays are always tangent to ${\mathit{CH}}(G)$. The following algorithm computes the boundary of the $\Theta$-region.

We first compute the clockwise sequence of guards $G'=\{g_1,\ldots, g_k\}$ defining the convex hull (see for example [@ps85]). Formalizing the intuition given above, we construct an algorithm that outputs circular arcs defining the boundary of the $\Theta$-region as follows. We identify all pairs $(g_i,g_j) \in G'\times G'$ with $g_i \ne g_j$, for which there exists an empty $\Theta$-cone that is tangent to $g_i$ and $g_j,$ and has its apex outside the convex hull. We say that the apex of the $\Theta$-cone can “see” the polygonal chain of ${\mathit{CH}}(G)$ from $g_i$ to $g_j.$ Such a pair $(g_i,g_j)$ will always have the property, that the lines supporting the convex hull edges $(g_j,g_{{\mathrm{succ}(j)}})$ and $(g_{{\mathrm{pred}(i)}},g_i)$ have an angle of intersection not greater than $\Theta,$ and that the lines supporting $(g_i,g_{{\mathrm{succ}(i)}})$ and $(g_{{\mathrm{pred}(j)}},g_j)$ have an angle of intersection greater than $\Theta$. The sequence of all these pairs $(g_i,g_j)$ and the corresponding circular arcs $C_{g_j,g_i}^{2\pi-\Theta},$ that are defined by $g_i,g_j,$ and the apex of the $\Theta$-cone that is tangent to $g_i$ and $g_j,$ can be computed by a cyclic scan over the sequence $G'.$ The arc end points of the $\Theta$-region boundary can be computed as the intersection points of each circular arc $C_{g_j,g_i}^{2\pi-\Theta}$ with the supporting lines through $(g_j,g_{{\mathrm{succ}(j)}})$ and $(g_{{\mathrm{pred}(i)}},g_i).$ Consequently the $\Theta$-region has the same complexity than the convex hull. The running time of the algorithm is dominated by the convex hull construction in $O(n\log n)$ time. We summarize the above in the following Lemma.

The boundary of the $\Theta$-region for $\Theta > \pi$ can be computed in time $O(n\log n)$ and its complexity is $|{\mathit{CH}}(G)|.$

The Boundary of the $\Theta$-Region {#s:boundary}
===================================

From now on we assume that the angle is $0<\Theta<\pi$. Here we give a mathematical description of the $\Theta$-region. First we come back to the inscribed angles and explain its meaning for our setting. Let $e=(l,r)\in G\times G$ be any pair of guards. Then the set of points where we can place the apex of an empty $\Theta$-cone passing through the line segment $(l,r)$ in the same direction is bounded by the circular arc, incident to $l$ and $r$ having inscribed angles $\Theta$, and its chord $lr$. We denote this closed circular segment with $D_{l,r}^\Theta$ (or $D_e$ for short) and its bounding circular arc, as above, with $C_{l,r}^\Theta$ (or $C_e$ for short). Because of the orientation, the circular segment is described uniquely.

The construction of the $\Theta$-region is motivated by the idea of locally removing sets $T_i$ of unguarded points from the convex hull ${\mathit{CH}}(G)$ such that the remaining part matches the $\Theta$-region (see Figure \[fig:shaperegions\], middle), i.e. we aim for $$\begin{aligned}
\label{for:uniontunnels}
\Theta\textrm{-region} = {\mathit{CH}}(G) \setminus \left( \bigcup_{i\in I} T_i \right)\end{aligned}$$ for specific sets $T_i$. Next we give the construction for the sets $T_i.$ Consider any empty $\Theta$-cone $c$ that has at least a guard on each ray (see Figure \[fig:tunnel\], left).

![The construction of a tunnel.[]{data-label="fig:tunnel"}](fig/tunnel){width=".8\columnwidth"}

First we turn the cone clockwise while pushing the cone towards the point set, such that it always stays empty but touches a guard on each boundary (see Figure \[fig:tunnel\], middle). We end this motion when the apex of the cone reaches the position of a guard, say $l_0.$ Afterwards we start again with cone $c$, i.e. in the original position, and rotate the cone in a similar way counterclockwise until the apex reaches the position of another guard, say $r_0.$ We extend our notions. With $L_i$ (resp. $R_i$) we denote the set of guards that are incident to the left (resp. right) ray of a cone during the construction (the white points in Figure \[fig:tunnel\], right). We call the closure of the union of all cones, which are used during the construction, the *tunnel $T_i$ with respect to $L_i$ and $R_i$*, or tunnel for short (shaded region in Figure \[fig:tunnel\], right). Note that the index set $I$ in Formula (\[for:uniontunnels\]) enumerates over all tunnels.

Note that Formula (\[for:uniontunnels\]) describes the $\Theta$-region of $G,$ because each empty $\Theta$-cone that intersects ${\mathit{CH}}(G)$ lies in at least one tunnel $T_i$: Let $c$ be such a cone. We can identify a tunnel by moving $c$ in the direction of its medial axis until one of its rays is tangent to a guard. Then we let the empty cone slide along that point without rotation until the second ray is also tangent to a guard. According to our construction there is a tunnel that contains this cone and hence the cone $c$ in its original position.

No point in $T_i$ is $\Theta$-guarded, but only its boundary can contribute to the boundary of the $\Theta$-region. First we consider its straight-line boundaries. Since $\Theta<\pi$, each point of a straight-line boundary can be crossed infinitesimally by an empty $\Theta$-cone. That means, there are open neighborhoods of unguarded points around each point of a straight-line boundary, and hence they can not contribute to the $\Theta$-region boundary. Points beyond the straight-line boundaries belong to different tunnels and will be processed independent from $T_i.$

Therefore we only have to consider the curved boundary of $T_i.$ Observe that during the construction, the apex of the rotating cone is drawing a *sequence of circular arcs* between $l_0$ and $r_0$ which we will formalize next. We define the set $$\begin{aligned}
\label{bigintersection}
  U_i \,:= \bigcap_{(l,r)\in L_i\times R_i} D_{l,r}^\Theta
  \end{aligned}$$ as the intersection of all circular segments for guard pairs in $L_i\times R_i.$ In the following Lemma we state that we can derive the curved boundary of $T_i$ from these circular segments. Let $h_i$ be the closed half plane which is bounded by the line through $l_0$ and $r_0$ and contains the sequence of arcs.

\[lem:tunnel\] Let $T_i,$ $U_i,$ and $h_i$ be as defined above. Then $T_i \cap h_i = U_i.$

[**(Superset.)**]{} Let $p\in U_i.$ Assume there is no empty cone with apex $p$ through tunnel $T_i.$ This means that there is at least a pair $(l,r)\in L_i\times R_i$ with the property that $\angle l p r<\Theta$. Hence $p\not\in D_{l,r}^\Theta$ which is a contradiction. [**(Subset.)**]{} Let $p$ be the apex of an empty $\Theta$-cone through tunnel $T_i.$ This means that $\angle l p r\ge\Theta$ for all $(l,r)\in L_i\times R_i,$ and hence $p$ lies in all corresponding circular segments $D_{l,r}^\Theta$.

It follows that the $\Theta$-region boundary is contained in the curved boundary of the union of the sets $U_i,$ i.e.$$\begin{aligned}
\label{f:complexity}
  \partial\Theta\textrm{-region}
  \;\subseteq\;
  \partial
  \bigcup_{i\in I} U_i
  \; = \;
  \partial
  \bigcup_{i\in I}
  \left( \bigcap_{(l,r)\in L_i\times R_i} D_{l,r}^\Theta \right),\end{aligned}$$ where $i$ enumerates over all tunnels. We observe that the intersections of $|L_i|\cdot |R_i|$ circular segments $D_{l,r}$ in Formulae (\[bigintersection\]) and (\[f:complexity\]) are too pessimistic. During the construction of a tunnel we collect all guard pairs $(l,r)\subset L_i\times R_i,$ that are incident to the rotating cone simultaneously, in $E_i$. Since the touching point of $L_i$ (resp. $R_i$) can only change in one direction to its neighbor in the sequence of $L_i$ (resp. $R_i$), that leads to a set $E_i$ of size $|L_i|+|R_i|-1$. Therefore we may reduce the intersection of the circular segments in Formula (\[bigintersection\]) to $$\begin{aligned}
\label{f:ui-reduced}
U_i:= \bigcap_{(l,r)\in E_i} D_{l,r} \cap h_i\end{aligned}$$ for which Lemma \[lem:tunnel\] is still valid. With ${\cal C}$ we denote the set of all circular arcs that appear in the boundary of a set $U_i$.

Upper Bounds on the Worst-Case Complexity {#s:upperbounds}
=========================================

Now we discuss the worst-case complexity of the $\Theta$-region and state the asymptotic bounds in the number $n$ of guards and the reciprocal value of the angle, i.e. $\frac{1}{\Theta}.$ During the analysis of the complexity, we distinguish cases according to the value of $\Theta.$ We already know that the $0$-region is the empty set. Since $G$ is a discrete set the $\Theta$-region is also the empty set for values close to $0.$

\[l:minimaltheta\] The $\Theta$-region for $\Theta\le\frac{2\pi}{n}$ is the empty set.

Consider the $n$ rays emanating from a point $p\in{\mathbb{R}}^2\setminus G$ through the guards in $G.$ Then the rays form at least one empty cone with angle of at least $\frac{2\pi}{n}$ which contains an empty $\Theta$-cone. Hence $p$ is unguarded. We can argue similarly for the guards $p\in G.$

According to the right term in Formula (\[f:complexity\]) the complexity of the $\Theta$-region is hidden in an arrangement of circular arcs. Since there are at most $O(n^2)$ different circular arcs, two for each guard pair, the complexity of the $\Theta$-region is trivially $O(n^4).$ Now we show that the set $\mathcal{C}$ of circular arcs is of $O(\frac{n}{\Theta})$ size. Hence the complexity of the $\Theta$-region is $O(\frac{n^2}{\Theta^2}).$

\[tm:size\] The set $\mathcal{C}$ of circular arcs, which defines the boundary of the $\Theta$-region, is of $O(\frac{n}{\Theta})$ size.

Instead of counting the arcs directly we count their end points. Let $p$ be an arc end point of a tunnel as shown in Figure \[fig:algo\], left.

![An end point $p$ of a circular arc in the boundary of a tunnel (left). A situation that is described in the proof of Theorem \[tm:size\] (middle). The auxiliary construction that is described in the proof of Theorem \[t:almostlinear\] (right).[]{data-label="fig:algo"}](fig/proofs){width=".8\columnwidth"}

In this position a ray of the rotating cone is incident to two guards at once. We assume without loss of generality that two guards lie on the left ray. We focus on the guard $l_k$ that is closer to the apex and count how often a guard can be in this situation. Clearly the number is bounded by $n-1$ because there are no more other guards. On the other hand we observe that the empty $\Theta$-cones in this situation can not intersect each other beyond the second guard on the left ray (see Figure \[fig:algo\], middle). Hence there can be at most $\lfloor \frac{2\pi}{\Theta} \rfloor$ different such cones. With the same argumentation for the right ray we bound the number of arc end points per guard by $2\lfloor \frac{2\pi}{\Theta} \rfloor$ and hence the total number of arc end points by $O(\frac{n}{\Theta}).$

From the last Theorem we can derive, that if the angle $\Theta>\delta$ is bounded by a constant $\delta>0,$ then the number of arcs in ${\cal C}$ is $O(n)$ and the complexity of the $\Theta$-region is $O(n^2).$ With an auxiliary construction we can even further improve this result.

\[t:almostlinear\] If the angle $\Theta>\delta$ is bounded by a constant $\delta>0,$ then the complexity of the $\Theta$-region is $O(n^{1+\epsilon})$, for any $\epsilon > 0$.

We make use of the following construction. Let $a\in{\cal C}$ be an arc in the boundary of tunnel $T_i,$ and let $u$ and $v$ be the end points of $a.$ The line segment $(u,v)$ and $a$ are the boundary of a circular segment, say $d_a.$ Now we clue a triangle $t_a$ at the edge $(u,v)$ of $d_a,$ which has an angle of $\min\{\Theta,\frac{\pi}{4}\}$ at $u$ and $v,$ and denote this new object with $F_a:= d_a \cup t_a$ (see Figure \[fig:algo\], right). We state that the triangle $t_a$ is a subset of $T_i$: Assume there is a guard $g\in t_a.$ Then the angles $\angle guv$ and $\angle gvu$ are smaller than $\Theta.$ Hence two empty $\Theta$-cones with apexes $u$ and $v$ would belong to different tunnels what is a contradiction to $a\subset\partial T_i.$ Furthermore, because of the angle at $u$ and $v$ the set of empty $\Theta$-cones with apexes at points in $a$ have to cover $t_a,$ what completes the proof of the statement.

We repeat the above construction for each arc $a\in{\cal C}$ and collect the new objects $F_a$ in the set ${\cal F}.$ We repeat the definition of $\alpha$-fatness from Efrat et al. [@efrat97]: *An object $F$ is *$\alpha$-fat* for some fixed $\alpha>1,$ if there exist two concentric disks ${\cal D}\subseteq F \subseteq {\cal D'}$ such that the ratio $\frac{\rho'}{\rho}$ between the radii of ${\cal D'}$ and ${\cal D}$ is at most $\alpha.$* We state that there is an $\alpha>1$ such that the objects $F_a\in{\cal F}$ are $\alpha$-fat: The worst-case scenario occurs when the arc $a$ is almost a straight-line. Hence we concentrate on the proof that the triangle $t_a$ is $\alpha$-fat (see again Figure \[fig:algo\], right). Remember that the angle at $u$ is $\min\{\Theta,\frac{\pi}{4}\}.$ Then the ratio between the radii of the circumcircle and the inscribed circle is $$\begin{aligned}
\frac{\rho'}{\rho} =
\frac{1}{\sin(\frac{1}{2}\cdot\min\{{\Theta},\frac{\pi}{4}\})}
\le
\frac{1}{\sin(\frac{\delta}{2})}
=: \alpha,\end{aligned}$$ which is a constant. Without loss of generality we assume $\delta\le\frac{\pi}{4}.$

The main Theorem in Efrat et al. [@efrat97] states, that the combinatorial complexity of the union of a collection ${\cal F}$ of $\alpha$-fat objects, whose boundary intersect pairwise in at most $s$ points, is $O(|{\cal F}|^{1+\varepsilon})$, for any $\varepsilon>0,$ where the constant of proportionality depends on $\varepsilon,$ $\alpha,$ and $s.$

It is already shown that $\alpha$ is a constant and that the objects in ${\cal F}$ are $\alpha$-fat. The boundary of each convex object $F_a\in{\cal F}$ has always three edges: two line segments and a circular arc. Therefore the boundary of each pair of objects in ${\cal F}$ intersect in at most $s=10$ points. As we said above $|{\cal C}|\in O(n),$ and hence $|{\cal F}|\in O(n),$ because $\Theta$ is bounded from below by a constant $\delta$. Therefore the construction fulfills all preconditions to apply the Theorem of Efrat et al. which completes the proof.

Now we show that the complexity of the $\Theta$-guarded region is linear for angles $\Theta$ at least $\frac{\pi}{2}.$

\[piovertwo\] The complexity of the $\Theta$-region is $O(n)$ for $\frac{\pi}{2}\le\Theta<\pi$.

Let ${\cal J}$ be a set of $m$ Jordan curves, i.e. simply-closed curves. Kedem et al. [@kedem90] proved that if any two curves in ${\cal J}$ intersect in at most two points then the complexity of their union is $O(m)$.

For each set $U_i$ we define a Jordan curve $J_i$. Let $J_i$ be the curved boundary of $U_i$ from $l_0$ to $r_0$ connected with an auxiliary half circle $C_{r_0,l_0}^\frac{\pi}{2}$, i.e.$$\begin{aligned}
  J_i \,:= \partial
     \left( \bigcap_{(l,r)\in E_i} D_{l,r}^\Theta \cap h_i \right)
     \cup C_{r_0,l_0}^{\frac{\pi}{2}}.\end{aligned}$$ Note that the auxiliary half-circle lies in $T_i$ because $\Theta$ is obtuse. Note further that $J_i$ is the boundary of a convex region and that $J_i$ lies inside the circle that supports $C_{r_0,l_0}^\frac{\pi}{2}$. We repeat this construction for all tunnels $T_i$, with $i\in I$, and collect all curves $J_i$ in ${\cal J}$. We state that any two curves in ${\cal J}$ intersect at most twice. Now assume that there are two curves $J_i, J_j \in {\cal J}$ which intersect in more than two points. We distinguish the following cases as they are shown in Figure \[fig:cases\].

![(Proof of Theorem \[piovertwo\].) The cases that could imply more than just two intersection points between the curves $J_i$ and $J_j$. The dotted parts are the sequence of arcs of $U_{i}$ and $U_{j}$ from $a$ to $b$ and from $c$ to $d$, respectively, and the solid arcs are the auxiliary half-circles.[]{data-label="fig:cases"}](fig/cases){width=".8\columnwidth"}

Let $A_{i}$ (resp. $A_{j}$) denote the sequence of circular arcs of $U_i$ (resp. $U_j$).

In Case 1, the sequence of circular arcs $A_{i}$ and $A_{j}$ intersect in point $p$ as is shown in Pictures (1a) or (1b). That means that for each tunnel $T_i$ and $T_j$ there exists an empty $\Theta$-cone with apex in $p$. Therefore the angle $\angle apb$ has to be at least $2\Theta$ which is at least $\pi$. That is a geometrical contradiction.

In Case 2, we consider a point $p$ that lies on the sequence of arcs $A_{j}$ outside $J_i$ as shown in Picture (2). The angle $\angle cpd$ is at least $\Theta$. By construction the angle $\angle bpa$ is larger than $\angle cpd$ and hence $\angle apb > \Theta$. It is a contradiction that $p$ does not lie inside $J_i$.

In Case 3, we consider an empty $\Theta$-cone with apex $c$ through tunnel $T_j$. Assume this cone passes between $a$ and $b$. Then the angle $\angle bca$ is at least $\Theta$ and hence $c$ has to lie inside $J_i$. This is a contradiction. In case that the empty $\Theta$-cone $c$ does not pass between $a$ and $b$, but $b$ and $c$, or $a$ and $d$, similar geometric contradictions can be shown.

Other cases are excluded since no guard can lie inside $J_i$ or $J_j$. This completes the proof.

Lower Bound on the Worst-Case Complexity {#s:lowerbound}
========================================

In the following we show that there is a sequence of inputs such that the asymptotic bound on the complexity of their $\Theta$-guarded region is $\Omega(n^2)$. For this purpose we give a generic construction for point sets $G_i$ with $n_i$ guards and angles $\Theta_i$ for all $i\in{\mathbb{N}}$, such that the complexity of the $\Theta_i$-region of the point set $G_i$ is lower bounded by $c\cdot n_i^2$ for some constant $c$ and $\lim_{i\to\infty}{n_i}=\infty.$ In fact $n_i$ is a linear function in $i,$ and $\Theta_i$ is of order $\frac{1}{i}.$ Therefore the complexity bound can also be interpreted as $\Omega(\frac{n}{\Theta})$.

First we motivate the construction for a given $i\in{\mathbb{N}}.$ To achieve the desired complexity, we construct the point set $G_i$ in such a way that the $\Theta_i$-region is fragmented into $c\cdot n_i^2$ connected components, each of constant complexity. Figure \[fig:squared1\] illustrates the idea of the construction.

![The location of the fragmented $\Theta_i$-region is located at the centre of the convex hull (left, $i=2$). Some connected components of the center are erased by unwanted tunnels (middle, $i=8$). All connected components of the center are protected against unwanted tunnels (right, $i=8$).[]{data-label="fig:squared1"}](fig/generic_example_1){width=".95\columnwidth"}

The area, where the $\Theta_i$-region is highly fragmented is at the center of the convex hull. The decomposition is forced by long, thin tunnels that enter this area ‘axis parallel’ from above, below, left, and right; more precisely the medial axis of the cones that enter these tunnels deepest are parallel to the principal axes. In the *first step* of the construction we determine the tunnels that force the fragmentation and implicitly determine the area (bounded by the box in Figure \[fig:squared1\]) that contains these connected component. Unfortunately the same guards, that define these tunnels, define an even larger number of unwanted tunnels which can enter this area as well. Therefore we have to place additional guards in the *second step* with the intention to prevent unwanted tunnels from entering this area, because they could erase some of the connected components, hence reducing the total complexity (see Figure \[fig:squared1\], middle and right). We show how to place a linear number of additional guards as obstacles in the plane to keep out a squared number of tunnels from this area. We note that because of the construction in the second step the convex hull can be huge compared to the box in which we count the connected components. For simplicity reasons we disregard the shape of the $\Theta_i$-region outside this box. The construction details are given below.

First step: To determine the *wanted* tunnels.
----------------------------------------------

We denote the square of edge length $2i$ that is centered at the origin and is oriented parallel to the principal axes with $B_i.$ In this step guards are placed on the boundary of the boxes $B_{4i}$ and $B_{2i}.$ The area, in which we will count the connected components, is $B_{i}$ (see Figure \[fig:squared3\], left).

![Placement of the guards in the first step for $i=2$ (left). Guard patterns A and B (right).[]{data-label="fig:squared3"}](fig/generic_example_3){width=".85\columnwidth"}

The entire construction is symmetric to the origin as well as to the principal axes. For this reason we only give the construction for the upper half of box $B_{4i}$; the constructions for the lower, left, and right half of this box are done analogously.

Now we introduce the guard patterns A and B (see Figure \[fig:squared3\], right), that define two ways to place guards inside a cell of width 1 and height $4i$, which we will use later on to stamp the upper half of the box with. First we define $\Theta_i$ as the angle[^2] between the rays emanating from $(\frac{1}{2},0)$ through the upper corners $(0,4i)$ and $(1,4i).$ To get guard pattern A we place four guards on the boundary of this cone: two with $y={2i}$ and two with $y=4i.$ These four guards define a wanted tunnel which is thin in the sense that the boundary of the tunnel stays in the box of width 1 for values $0\le y\le i$; remember that we only care for the interior of $B_i.$ For technical reasons we add guards at $(0,2i)$ and $(1,2i)$ to avoid unwanted tunnels between neighboring guard patterns A. In case we do not need a tunnel inside the cell we use pattern B: three guards that are placed equidistant on the top edge of the pattern make it impossible for any cone to enter this box from above deeper than $y=2i.$ Next we subdivide the upper half of the box $B_{4i}$ in $8i$ cells of width 1. The medial quarter is stamped with pattern A, the remaining cells are stamped with pattern B (see Figure \[fig:squared2\]).

![Subdivision of the upper half of $B_{4i}$ in $8i$ cells (left). The guard pattern for the upper half (right).[]{data-label="fig:squared2"}](fig/generic_example_2){width=".95\columnwidth"}

This way we can guarantee $2i$ wanted tunnels from above which intersect $B_i$ and touch the $x$-axis. After repeating this construction for the lower, left, and right half of $B_{4i}$, tunnels from above and below touch at the $x$-axis as well as tunnels from the left and right touch at the $y$-axis. This follows immediately from the symmetric construction. Removing these tunnels from the box $B_i$, yield to a fragmentation into $(2i+1)^2$ connected components.

Finally we remark that we can save up to 2 guards per stamped pattern if guards overlap with the neighboring pattern. Hence the number of guards, that are placed in the entire first step, sum up to $80i+4.$

Second step: To exclude the *unwanted* tunnels.
-----------------------------------------------

Again we start with the construction for the upper half of $B_{4i}.$ Figure \[fig:squared8\] shows the situation of the $2i$ neighboring guard patterns A. We denote the guard pairs on the line $y=4i$ with $P_1,\dots, P_{2i}$ and the guard pairs on the line $y=2i$ with $Q_1, \ldots, Q_{2i}.$

![All possible guard pairs through which empty cones can reach $B_i$ from above.[]{data-label="fig:squared8"}](fig/generic_example_8){width=".7\columnwidth"}

An empty cone that enters $B_i$ from above therefore has to pass through $P_k$ and $Q_\ell$ for some $k,\ell\in\{1,\dots,2i\}.$ If $k=\ell,$ the tunnel is wanted. So the task is to hinder all cones through tunnels with $k\neq\ell$ to intersect the box $B_i.$ We introduce a new notion to reformulate the problem.

Let $t$ be a tunnel through $P_k$ and $Q_\ell.$ We say that an empty cone enters tunnel $t$ *the deepest* if the $y$-value of its apex is minimal among all empty cones in $t$.

Note that the deepest cone in a tunnel is unique and is tangent to at least one guard on each ray. We define the *slope of a cone* as the slope of its medial axis. Because of the regular structure of the cells with guard pattern A we can make the following Observation. Informally it states that the slope of a deepest cone through $P_j$ and $Q_{j+h}$ is independent of $j$ and implicitly given by $h.$

\[obs:deepest\] Let $h\in\{0,\dots,2i-1\}.$ Let $c_j$ be the deepest cone through $P_j$ and $Q_{j+h}$ and let $d_j$ be the deepest cone through $P_{j+h}$ and $Q_{j}$ for all $j\in\{1,\dots,2i-h\}.$ Then all cones $c_j$ have the same slope, and all cones $d_j$ have the same slope.

W.l.o.g. we concentrate on the cones $c_j$, but we can argue in the same way for the cones $d_j.$ We derive from Observation \[obs:deepest\] that for fixed $h$ the intersection of all deepest cones $c_j$ is again a cone with the same slope (see Figure \[fig:squared6\], left).

![The deepest cones $c_j$ used in Observation \[obs:deepest\]. Here the vertical arrow marks the direction of their medial axis (left). The deepest cones that are tangent to the new vertex (middle). The deepest cones, in the case that the new guard is pulled far out in the direction of the former medial axis (right).[]{data-label="fig:squared6"}](fig/generic_example_6){width=".9\columnwidth"}

Assume we place a guard at a random position inside this intersection. Then [none]{} of the cones $c_j$ is empty anymore. That means that there are new deepest cones with different slopes, since they have to be tangent to the new guard (see Figure \[fig:squared6\], middle). Now we pull the new guard in the direction of the medial axis of the former deepest cones towards infinity. Then we observe, that while we move this point, the deepest cones are rotated and this way are pulled away from the $x$-axis. Since the limes of the rotation, compared to the slope of the original deepest cones $c_j$, has absolute value $\frac{\Theta_i}{2}$, we can force a rotation by an angle that is arbitrarily close to half of the apex angle, i.e. $\frac{\Theta_i}{2}-\varepsilon$ for any $\varepsilon>0$ (see Figure \[fig:squared6\], right). Note the generality of the above discussion for all $h=\{0,\dots,2i-1\}.$ We will definitely *not* place a guard in the *union* of the deepest cones for $h=0,$ since these tunnels force the decomposition of the $\Theta_i$-region in the center. In spite of this we have used exactly this case in the drawings in Figure \[fig:squared6\], since it depicts the worst-case scenario we will consider later in the proof.

Now we are able to complete the construction. First we compute the slope of the medial axes of the deepest cones $c_j$ as well as $d_j$ of Observation \[obs:deepest\] for all $h=\{1,\dots,2i-1\}.$ For each of these $4i-2$ slopes we place a guard at the intersection point of the ray emanating from the origin having this slope and the boundary of a new box $B_x$ (see Figure \[fig:squared10\], left).

![Construction of the second step for all parts: above, below, left, and right (left). Construction used in the proof of Lemma \[lem:unwanted\] (right).[]{data-label="fig:squared10"}](fig/generic_example_10){width=".7\columnwidth"}

Box $B_x$ has *necessarily* to be large enough to guarantee, that each intersection point lies

1.  outside the union of the wanted cones and

2.  inside the intersection of the deepest cones of the given slope.

The existence of box $B_x$ with these properties follows from the discussion above. But this is not *sufficient*. It remains to prove the following lemma.

\[lem:unwanted\] Box $B_x$ can be chosen large enough such that no empty $\Theta_i$-cone, but the wanted cones, can intersect $B_i.$

It is sufficient to prove the claim for the deepest cones with the minimum apex $y$-value amongst all deepest cones according to Observation \[obs:deepest\]. These are the cones for $h=0.$ (Please note that we do not block tunnels for $h=0$ in practice; we just prove that we could even hinder cones through these tunnels from entering $B_i.$)

Remember that we can place the guard which blocks the deepest cones such that the deepest cones are rotated by an angle arbitrarily close to $\frac{\Theta_i}{2}.$ W.l.o.g. we assume that the cone is rotated clockwise. Consider the empty cone $c$ of maximum angle with apex at $a=(\frac{1}{4},i)$ inside a cell with guard pattern A (shaded region in Figure \[fig:squared10\], right). This cone touches the boundary of $B_i$ and its left ray is vertical as it is the case for maximal rotated deepest cones. If we can show that the angle of $c$ is smaller than $\Theta_i$ it follows that $c$ can not enter $B_i$. We crop $c$ at the line $y=4i$ to make it a rectangular triangle. Now we take the $\Theta_i$-cone from pattern A, Figure \[fig:squared3\], and move its apex to $a.$ We divide the triangle along the right boundary of the $\Theta_i$-cone through point $(\frac{5}{8},4i).$ Consequently the left sub-triangle has angle $\frac{\Theta_i}{2}$ at point $a.$ Since the opposite leg of the entire triangle is 2-times the opposite leg of the left sub-triangle, the total angle of $c$ at $a$ is less than 2-times $\frac{\Theta_i}{2}.$

After repeating this construction for the lower, left, and right half we have placed $16i-8$ additional guards. Together with the guards from the first step they define the set $G_i$ with $n_i = 96i-4$ guards in total. The generic example presented in this section proves the following Theorem.

There is a sequence of inputs $(\Theta_i,n_i,G_i)_{i\in{\mathbb{N}}}$ with $\lim_{i\to\infty}\Theta_i=0$ such that the asymptotic bound on the complexity of their $\Theta$-region is $\Omega(n^2)$ where $n$ is the number of guards.

Algorithm {#s:algorithm}
=========

Here we discuss a way to compute the boundary of the $\Theta$-region. Note that we gave bounds on the worst-case complexity of the $\Theta$-region above. Clearly, for any $n$ and any $\Theta$ there are sets $G$ for which the $\Theta$-region is empty or extremely simple. Despite of this our algorithm will consider the $O(\frac{n}{\Theta})$ arcs in $\mathcal{C}$ and hence can not be output-sensitive. We allow a simplification in the presentation of the algorithm: We will consider a set $\mathcal{C'}$ of arcs which are longer on one side, i.e. $|\mathcal{C}|=|\mathcal{C'}|$ and $\bigcup \mathcal{C} \subset \bigcup \mathcal{C'}$.

First we compute the convex hull ${\mathit{CH}}(G)$ and add for each hull edge $(u,v)$ the circular arc $C_{u,v}^{\Theta}$ to the set $\mathcal{C'}$. For each guard $g$, that is not a vertex of ${\mathit{CH}}(G)$, we compute all empty cones of maximal angle with apex at $g$ together with two guards (witnesses) $g_{\min}$ and $g_{\max}$ per empty cone, which lie on its rays. (See the light shaded cone in Figure \[fig:algo2\].) This can be done by using the algorithm of Avis et al. [@avis] in $O((\frac{n}{\Theta})\log n)$ time and $O(n)$ space.

![Guard $g$ can contribute to at most two end points for each maximal empty cone with apex $g.$[]{data-label="fig:algo2"}](fig/algo_2){width=".25\columnwidth"}

As we did in the proof of Theorem \[tm:size\], we find the arcs in $\mathcal{C}$ via their end points. If we move an empty $\Theta$-cone with apex $g$ and its left ray through $g_{\min}$ along the line through $g$ and $g_{\min}$ until a guard, say $g_{r}$, is tangent to the other ray, the new apex marks an end point $p_r$ of two arcs in the set $\mathcal{C}$ (see Figure \[fig:algo2\]). Since we do not know the second end points of the arcs, we add the piece of $C_{g_{\min},g_r}^\Theta$ to $\mathcal{C'}$ that ends in $g_{r}$ and ${p_r}$, and we add the piece of $C_{g,g_r}^\Theta$ to $\mathcal{C'}$ that ends in $g$ and ${p_r}$, A similar construction for the line through $g$ and $g_{\max}$ will add another two arcs to $\mathcal{C'}$.

Note that by fixing the line through $gg_{\min}$ we can find guard $g_r$ naively by simply inspecting all guards in $G$, and similarly we can find $g_l$ for the line through $gg_{\max}$. However, one can compute guards $g_r$ and $g_l$ faster with the help of the well-know *Partition Theorem* that has been extensively used in the context of range searching. We cite the theorem for a planar point set.

(Partition Theorem [@Matousek].)\[TM:Partition\] Any set $S$ of $n$ points in the plain can be partitioned into $O(r)$ disjoint classes by a simplicial partition, such that every simplex (i.e. triangle) contains between $\frac{n}{r}$ and $\frac{2n}{r}$ points and every line crosses at most $O(r^{\frac{1}{2}})$ simplices (crossing number). Moreover, for any $\xi > 0$ such a simplicial partition can be constructed in $O(n^{1+\xi})$ time.

Using this Theorem recursively one can construct a tree which is called a *partition tree* (e.g. the root of the tree, associated with $S$, has $O(r)$ children, each associated with a simplex from the first level, and so on). From now on we assume that $r$ is a constant. Observe that if $r$ is a constant, the partition tree is of $O(n)$ size and it can be constructed in $O(n^{1+\xi})$ time for any $\xi>0$.

For any $\xi>0$, there is a data structure of $O(n\log n)$ size and $O(n^{1+\xi})$ construction time such that for the given lines through $gg_{\min}$ and $gg_{\max}$, corresponding guards $g_l$ and $g_r$ can be computed in additional $O(n^{\frac{1}{2}+\xi})$ time.

Assume we are given a partition tree and suppose that we fix the line through $gg_{\max}$. Clearly by Theorem \[TM:Partition\] we have the bound on the number of triangles that intersect the line which is $O(\sqrt{r})$. On those triangles we recur, which leads to a total of $O(\sqrt{n})$ triangles intersected by the line. But still there might be $O(r)$ triangles lying completely to the left of the line $gg_{\max}$. For those triangles we can precompute a convex hull for the points inside each triangle. This will increase the total space of the partition tree by a $O(\log n)$ factor since every level in the tree now will be of $O(n)$ size. However, this way we avoid recursing on the triangles that lie completely to the left of $gg_{\max}$. Namely, for every triangle that lies to the left of $gg_{\max}$, guard $g_l$ can be found as an extreme point of the precomputed convex hull in the direction perpendicular to the line that forms the $\Theta$-cone with the line through $gg_{\max}$ in $O(\log n)$ total time (see [@orourke00], Section 7.9). The case for the line through $gg_{\min}$ is similar.

Therefore we can state the following Lemma.

For any $\xi>0$, the set $\mathcal{C'}$ can be computed in $O(n^{\frac{3}{2}+\xi}/\Theta)$ time and $O(n\log n)$ space.

Next we discuss how to compute the $\Theta$-guarded region from the set of circular arcs $\mathcal{C'}$. For each connected component of the $\Theta$-region the algorithm outputs a sequence $p_1,\ldots, p_k$ of points in the plane and circular arcs incident with pairs $p_{i-1}, p_i$ for $i=2,\ldots, k$ and $p_k, p_1$ as edges of the $\Theta$-region.

We start with computing the [arrangement]{} $\mathcal{A}(\mathcal{C'})$ of set $\mathcal{C'}$. Let $\psi$ denote the number of cells in $\mathcal{A}(\mathcal{C'})$ and let $\mu$ denote the total complexity of the arrangement $\mathcal{A}(\mathcal{C'})$, which upper bounds the complexity of the $\Theta$-region. Edelsbrunner et al. [@edelsbrunner92] showed that $\mu$ is at most $O(\sqrt{\psi} (\frac{n}{\Theta}) 2^{\alpha(n)})$, where $\alpha(\cdot)$ is the inverse Ackerman function which is an extremely slow-growing function. Moreover, the arrangement $\mathcal{A}(\mathcal{C'})$ can be constructed in $O((n+\mu) \log n)$ time by the plane-sweep algorithm of Bentley and Ottman [@bo79]

Since arcs in $\mathcal{C'}$ are bounding circular segments from the Formula (\[f:complexity\]), cells in the arrangement $\mathcal{A}(\mathcal{C'})$ will have the property that they are either $\Theta$-guarded or not $\Theta$-guarded. Hence, if some point from the cell is $\Theta$-guarded then the whole cell belongs to the $\Theta$-region and opposite. Let $P$ denote the set of $\psi$ different points such that each point is taken from the interior of $\psi$ different cells in $\mathcal{A}(\mathcal{C'})$. To detect the cells that belong to the $\Theta$-region, we use the following lemma.

\[lm:avis\] Let $G$ be a set of $n$ guards and let $P$ be a set of $\psi$ query points in ${\mathbb{R}}^2$. The $\Theta$-unguarded points of $P$ can be reported together with their witnesses $g_{\min}$ and $g_{\max}$ in $O(\frac{n+\psi}{\Theta}\log (n+\psi))$ time and $O(n)$ space.

Avis et al. [@avis] presented an algorithm to compute all $\Theta$-unguarded guards of $G$ in $O(\frac{n}{\Theta}\log n)$ time and $O(n)$ space. So far the set of query points and the set of guards are the same. But since their algorithm actually distinguishes between query points and guards, it can be extended immediately: In Steps 2 and 3 of procedure *Unoriented Maxima* on page 284f. only guards are inserted into the convex hull constructions, while tangents to these convex hulls are only computed through query points. The running time of the algorithm is dominated by sorting the points in $G\cup P$ for $\frac{\pi}{\Theta}$ many directions which takes $O(\frac{n+\psi}{\Theta}\log (n+\psi))$ time. For more details see Section 2 and Section 6 (Appendix) in [@avis].

At the end we collect all $\Theta$-guarded cells and output the sequence of nodes and edges on the boundary of the union of them. We conclude with the following Theorem.

For any $\xi>0$, the $\Theta$-region for $\Theta < \pi$ can be computed in time $O(n^{\frac{3}{2}+\xi}/\Theta + \mu \log n)$, where $\mu$ denotes the complexity of the arrangement $\mathcal{A}(\mathcal{C'})$.

Conclusion {#s:conclude}
==========

In this paper we consider a point to be guarded, if it is guarded from ’all’ sides by a given finite set of guards $G$. Our main goals were to analyze the shape and the complexity of the $\Theta$-region, i.e. the set of all $\Theta$-guarded points, and give a mathematical description of it.

As a result, we showed that the $\Theta$-region is defined by a set of at most $O(\frac{n}{\Theta})$ many circular arcs. The difficulty in the complexity analysis of the $\Theta$-region itself appeared while arguing about the complexity of the union of convex sets $U_i$ which are bounded by these arcs (cf. Formula \[f:complexity\]). In dependency on $\Theta$ we summarize our results on the worst-case complexity of the $\Theta$-region in Table 1. Furthermore, we could give a series of inputs with decreasing angle and increasing number of guards whose asymptotic complexity is $\Omega(n^2)$. Finally we gave an algorithm to compute the $\Theta$-region.

[|@c@|@c@|]{}

------------------------------------------------------------------------

angle $\Theta$ & worst-case complexity\

------------------------------------------------------------------------

$\pi\le\Theta<2\pi$ & $|{\mathit{CH}}(G)|$ vertices\
$\frac{\pi}{2}\le\Theta<\pi$ & $O(n)$\
$ \delta <\Theta<\frac{\pi}{2},$ for constant $\delta>0$ & $O(n^{1+\varepsilon}),$ for any $\varepsilon>0$\

Appendix: Technical Mistakes in a Recent Publication
====================================================

Abellanas et al. [@ACM08] claim the complexity of the $\Theta$-region to be $O(n)$ for a fixed value of $\Theta\in(0,\pi]$ and suggest an algorithm to compute it. Because the paper is not precise in several places, we will point out mistakes that show gaps in the proofs of the main results.

### Mistake in the Construction. {#mistake-in-the-construction. .unnumbered}

The entire construction, and hence the results, are based on the existence of certain arc chains, one per convex hull edge, which are introduced in Definition 4 on page 367. But Definition 4 is actually a characterization of a point-set. That means Definition 4 contains a *hidden and unproved Lemma,* stating that the defined point-set forms a chain of arcs. In the context of other mistakes we will argue below that these chains *do not exist in general for acute $\Theta<\frac{\pi}{2}.$*

We begin with Definition 3 on page 366. (Be aware of the index typos.) It is stated that a guard pair $(s_i,s_j)$ can only be entered by empty cones from one direction, and hence one of the two connecting arcs is excluded a priori. But this is not generally true for $\Theta<\frac{\pi}{2}$ as the guard pair $(a,c)$ in Figure \[fig:mistakes\_4\] shows. In the following we assume that, however, both directions can be distinguish and handled somehow.

Next we focus on the construction of the chain as is given in the proofs of Lemma 3 and Lemma 4 on pages 368–370. There vertices are connected via two arc pieces to a predecessor and a successor only, guaranteeing a vertex degree of 2 by construction.

Because of the mentioned mistake in Definition 3, there is now a misunderstanding of the terms predecessor and successor of an arc end point: The predecessor (resp. successor) is the left (right) end point of the connecting arc piece *viewed from the direction of the empty cone* that supports this arc. (By the way, this cannot be decided only by the $x$-coordinate of guards, as is assumed for the partitioning of the set $M_{s_k,s_{k+1}}$ in the left column, above Figure 3, on page 367.)

![Example that guards can not be ordered linearly for $\Theta<\frac{\pi}{2}$ in all cases.[]{data-label="fig:mistakes_4"}](fig/mistakes_4){width=".6\columnwidth"}

Now we have a look at *our* Figure \[fig:mistakes\_4\]. There $(s_k,s_{k+1})$ is a convex hull edge and $a,$ $b,$ $c$ denote guards. There may be also additional (shaded) guards but we rely on the existence of the three empty (shaded) cones. Then $D,$ $E,$ and $F$ denote non-empty arc pieces on the pairwise arc chains (dotted lines) between these guards. During the construction the guards (even if they are removed later on) and arc pieces get their position in the chain that belongs to the convex hull edge. We derive an order on these objects from the empty cones: $c\prec D\prec a$ and $a\prec E\prec b$ and $b\prec F\prec c.$ These constraints on the order can only be satisfied by a loop that contains these guards and arc pieces, since every vertex has degree 2. This contradicts the assumption of the existence of an arc chain.

#### Remark:

Because of this general argumentation, we are convinced that the task of finding the $\Theta$-region has to be motivated, however, rather by the directions of empty cones than by the convex hull edges. (Note that each instance of the generic example in Section \[s:lowerbound\] can be embedded in a huge box with just four hull edges.)

### Mistake in the Complexity Statement. {#mistake-in-the-complexity-statement. .unnumbered}

In Proposition 2 on page 370 the complexity of the $\Theta$-region is claimed to be linear for any fixed value of $\Theta.$ Below we point out that this complexity bound is not justified in the [most crucial]{} step of the proof, hence *leaving a gap in the proof.*

The proof begins with a consideration on the boundary of the $\Theta$-region restricted to a convex hull edge ${(s_k,s_{k+1})},$ i.e. cones can now only enter the hull through ${(s_k,s_{k+1})}.$ It is stated, that the boundary is the chain of arcs that corresponds to this edge and that it has linear size. Although we have proven above that this chains do not exist in general for $\Theta<\frac{\pi}{2},$ and hence we do not know anything about the complexity of a proper replacement for these chains, *we assume just for the sake of argumentation* that this would be true, however.

In the second half of the proof the total number of vertices in all arc chains is estimated. But what is missing in the counting argument for the complexity of the union of the $\Theta$-regions, that are restricted to a convex hull edge, are the *intersections between these restricted $\Theta$-regions.* (Remember that we have built our examples with quadratic complexity [only]{} on this kind of intersections in Section \[s:lowerbound\].) No characteristic of the objects is given here, why the complexity of the union should be $O(n)$ for fixed values of $\Theta;$ even fatness and convexity seem not to be strong enough for this claim.

The whole proof of this Proposition seems to go much more along the line of proving that the $\Theta$-region can be *described* by a linear number of arcs, which we have also proven in Theorem \[tm:size\], than arguing about the complexity of the $\Theta$-region itself. Without further argumentation there is just an upper bound of $O(n^2)$ on the complexity for constant angles since the $\Theta$-region is embedded in the arrangement of $O(n)$ arcs.

[99]{}

M. Abellanas, A. Bajuelos and I. Matos. Some Problems Related to Good Illumination, , 2007, pp. 1–14.

M. Abellanas, M. Claverol and I. P. Matos. , 2008, pp. 365–372.

P. K. Agarwal, B. Aronov and M. Sharir.

D. Avis, B. Beresford-Smith, L. Devroye, H. Elgindy, E. Guévremont, F. Hurtado and B. Zhu. Vol. 28, 1999, pp. 278–296.

J. L. Bentley and T. Ottman. , Vol. 28, 1979, pp. 643–647.

B. Chazelle. Vol. 31, No. 4, 1985, pp. 509–517.

V. Chvátal. Vol. 18, 1975, pp. 39–41.

R. Cole, M. Sharir and C. Yap. Vol. 16(1), 1987, pp. 61–67.

H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel and M. Sharir. Vol. 92, Issue 2, 1992, pp. 319–336.

H. Edelsbrunner, D. G. Kirkpatrick and R. Seidel. Vol. 29, No. 4, 1983, pp. 551–559.

A. Efrat and M. Sharir. ,

K. Kedem, R. Livne, J. Pach and M. Sharir.

J. Matousek.

J. O’Rourke. 1987.

J. O’Rourke. , 2nd Edition,

F. P. Preparata and M. I. Shamos. 1985.

M. Sharir and P. K. Agarwal. 1996.

J. Urrutia. in J[ö]{}rg-R[ü]{}diger Sack and Jorge Urrutia, editors, [*Handbook of Computational Geometry*]{}, 2000, pp. 973–1027.

[^1]: Exceptionally we consider closed cones here.

[^2]: Note that $\Theta$ and $i$ are not independent because $\Theta=\arctan(\frac{1}{8i}) \le \frac{1}{8i}.$


1. Field of the Invention
This invention relates in general to methods and apparati for calculating the image focus on cathode ray tubes.
When monitors and television sets are manufactured, not only the electrical values must be tested and adjusted, but also the image geometry and other image parameters must be set.
The automation of image adjustment not only makes it cheaper to manufacture such equipment, but also increases the yield and improves the quality of the sets.
Identification of image height, image width, image position and image brightness can, for example, be accomplished with known sensor systems. By contrast, the automatic identification of the image focus is very difficult to realize and requires very expensive equipment.
An additional problem is acquiring images from monitors or television sets having different standards. There are television sets that operate with 50 Hz or with 60 Hz field frequencies; in a monitor assembly line, for example, monitors that have three different field frequencies must be adjusted.
The invention enables the adjustment of the image focus of monitors, including those having different field frequencies, at a reduced cost and reduced complexity of apparatus.
2. Description of the Prior Art
Images, scripts, and graphics are produced on cathode ray tubes for television monitors. An optimum image focus is desired and since the image focus can differ at different locations on the monitor screen, the entire image content must be utilized for evaluating the image focus.
Until now, the picture screen of a monitor has been observed by the human eye. With adequate training, an employee looking at the picture screen can recognize the difference between the image focus at the edge and the focus in the middle. The adjustment of image focus occurs by adjusting a potentiometer in the deflection assembly.
Until the present time, such a procedure could only be automated using an extremely expensive apparatus.
For the automatic adjustment of the image focus, measuring marks on a part of the monitor image are recorded, for example by a solid state camera, with known methods. The camera signal is interpreted and the image focus is obtained with special and complicated hardware logic.
When monitors with multiple field frequencies must be adjusted, the known solution for 50 Hz monitors can only be applied in principle. An extension of the method would require further development of the hardware circuitry and of the method of measuring the average image focus over the entire image, such that a rapid adaption to the various field frequencies is possible.
It is known also known how to measure the image focus by way of the gradient distribution in the gray-scale image using an involved image processing system. In addition to the high cost for hardware and software, there is the disadvantage as in the previously discussed solution that an average image focus must be calculated using many measurements at different locations of the CRT screen. The time to acquire the image focus thus is usually too long. Times of a few hundred milliseconds are desirable in automated manufacture.
The following art discusses various cathode ray tube adjustment and monitoring systems. U.S. Pat. No. 4,163,308, U.S. Pat. No. 4,411,120, U.S. Pat. No. 3,962,722, U.S. Pat. No. 4,551,653, U.S. Pat. No. 4,193,086, European Patent No. 105,792, Patent Abstracts of Japan, Vol. 10, No. 297 of Oct. 9, 1986, No. 61-114437, the article entitled "A Technique for the Automated Measurement of the Resolution of Shadow Mask CRT Displays" by Veron and P. O'Callaghan SID 87 Digest Pages 211-213, German No. 2,030,417, German No. 2,805,691, German DE No. 3,107,042, German No. 2,746,969, German DE No. 3,047,340, German DE No. 2,839,187, French No. 2,497,399, European patent No. 0,119,282 and publication in Funkschau of May 1986, Pages 40-42.


Q:

Can "to seed" and "to sow" be used interchangeably?

I'd never heard about "to sow" until recently, and I was quite surprised that I couldn't find even a connotation about the difference in meaning from "to seed."
The German word "säen" is translated with both "to seed" and "to sow", neither of them are marked dialect or old-fashioned or anything.
Wiktionary defines them as:

to seed: To plant or sow an area with seeds.
to sow: To scatter, disperse, or plant (seeds).

As a non-native speaker, I fail to see the difference here (especially when one is defined using the other).
In this sense, can they be used interchangeably?

A:

No, they can't always be used interchangeably. To sow seeds is to put or spread them where you want them to grow, or you can speak of sowing a particular type of plant. You can seed a patch of ground (sow seeds on it), but 'seed' as a verb can also mean to produce seeds (of a plant), to remove the seeds from a fruit, as well as the various metaphorical uses mentioned by user067531.

A:

I think that one main difference is the financial/tech usage of seed vs sow:

Transitive To seed (Wiktionary) :

To start; to provide, assign or determine the initial resources for, position of, state of.
A venture capitalist seeds young companies.
  The tournament coordinator will seed the starting lineup with the best competitors from the qualifying round.
  The programmer seeded fresh, uncorrupted data into the database before running unit tests.

The usage in sports, especially in tennis, is also worth mentioning.

To be able to compete (especially in a quarter-final/semi-final/final).
The tennis player seeded into the quarters+tennis.

Sporting (originally tennis) sense (1898) is from notion of spreading certain players' names so as to ensure they will not meet early in a tournament. (Etymonline)

A:

I would just point out that while you can "sow the seeds", you should not "seed the sows".


[Investigation of the health-related quality of life after a dorso ventral stabilization of the thoracolumbar junction].
Combined dorsoventral stabilization provides superior mechanical stability in the operative treatment of thoracolumbar spine fractures. Currently, there are no data available reflecting the quality of life in trauma patients following the combined procedure. The aim of this investigation was to study the health-related quality of life after dorsoventral stabilization of the thoracolumbar junction using the SF-36 Health Survey. In order to assess the quality of life, 30 patients from a consecutive series with unstable fractures of the thoracolumbar junction were investigated in a clinical study. After posterior stabilization with an internal fixator (USS, Synthes),anterior arthrodesis was performed subsequently by autogenous iliac bone grafting in combination with osteosynthesis (MACS, Aesculap; VentroFix, Synthes). The quality of life was investigated 2 years after surgery. Additionally, plain X-rays were obtained and the degree of kyphotic deformation was measured. The evaluation of the data obtained from the SF-36 revealed a reduced quality of life, especially regarding the "physical functioning index", the "bodily pain index", and the "emotional functioning index". Of the patients, 42% still suffered from moderate to severe pain. Measurement of the Cobb angle showed a slight loss of correction without occurrence of a relevant kyphotic deformity. Our statistical analyses did not show any correlation between the data obtained from the SF-36 and the clinical results. Especially there was no correlation between the "bodily pain index" and the Cobb angle ( r=0.112, Spearman's rank order correlation). The patients studied here showed a reduced quality of life 2 years after dorsoventral stabilization of the thoracolumbar junction predominantly resulting in long-term pain symptoms. As these findings could not be related to the radiological results (i.e., the occurrence of a kyphotic deformation), other factors such as injury of the motion segment of the spine and the major surgical procedure have to be considered as the main reasons for the reduced quality of life. In summary, it can be concluded that the SF-36 is a suitable tool for the investigation of the postoperative outcome following dorsoventral stabilization of the thoracolumbar junction in trauma patients.


The United States and others may have limited leverage over Kenya’s domestic politics, but they are not without options that would significantly improve the prospects for acceptable elections and help avert a major crisis. However, with little more than two months before the elections, Washington must intensify its engagement or forsake its opportunity to make a difference.

But the window might be closing fast on the international community to help Kenya avoid a repeat of 2007-08, when 1300 died and 300,000 were displaced after a bungled election. According to a report by the Global Commission on Elections, Democracy and Security (yours truly was a research assistant for the commission), evidence suggests that international interventions to encourage reasonably free and fair and peaceful elections are most effective when done well in advance to the polling day. In the Kenyan case, the structural causes of previous rounds of electoral violence were never addressed, and may yet lead to the loss of life this election cycle.

What can now be done to avoid large scale organized violence is to credibly convince the politicians and those who finance youth militia (chinkororo, taliban, mungiki, jeshi la mzee, baghdad boys, etc) that they will be held accountable. So far, as is evident in Tana River and the informal settlements within Nairobi, the lords of violence appear to be operating like it is business as usual.

WASHINGTON (Reuters) - The Trump administration is considering new sanctions against Russia in response to election meddling and a devastating cyber attack last year, senior U.S. officials said on Wednesday, pushing back against criticism that it has been slow to act.

SEOUL (Reuters) - South Korea spent around 240 million won ($223,237) on the younger sister of North Korean leader Kim Jong Un and her entourage during their three-day visit for the Pyeongchang Winter Olympics, a government official said on Thursday.


REALTOR Resources

Coming Soon riders can be a boon – or a bane – for REALTORS. What started as a marketing tactic in the foreclosure industry has blossomed into a common practice for many agents in a very busy sellers’ market. Used properly, a Coming Soon rider can be a way to get some advanced marketing out on a property while the owners are finishing getting it ready for sale. But the abuse of the rider has led to some really negative consequences for both consumers and the industry. Buyers’ agents were having a hard time getting in to properties before they were sold and sellers weren’t being exposed to the entire market – potentially limiting their contract offers. Properties sold before they are listed in the MLS can also interfere with appraisers and those who are trying to find good comparables for future sales.

To encourage the proper and fair use of the idea of a property that is “coming soon,” the MLS has created a new status for listings.

Another advantage of the Coming Soon status is that you’re able to enter listing data with limited information, so if you’re still trying to round up some final pieces like room sizes or HOA information you can still get the basic information into the MLS under the Coming Soon status, whereas you might be required to have that information if you were entering a property into Active status. You’ll still be able to alert other agents that the property will be available for showings at a later date.

How long can properties have a Coming Soon status?

Listings under the Coming Soon status can remain at that status for up to 14 days. You may change a listing to Active at any time during those 14 days.

What happens after 14 days if I haven’t changed the status to Active?

Listing agents will receive a reminder notice three days prior to the expiration of the coming soon period for their listings. If the property status is not changedat the end of the 14 days, the status will automatically change to Temporarily Off Market. The listing will remain in that status until the listing agent changes it or it expires on its expiration date. The property may not be relisted under the Coming Soon status within one year unless it has been sold or leased within that year. This is to prevent abuse of the Coming Soon status.

Can Coming Soon properties be shown?

Whether or not you can open properties for showings while they are in the Coming Soon status depends on your office policy. The MLS rules do not prevent showings. Do remember to follow best practices and keep everyone’s safety in mind – especially if renovations are ongoing or pets are present.

Will external sites have access to Coming Soon property information?

Third party sites will not get information about properties in the Coming Soon status. Agents are able to search for properties under this status if they are members of the MLS. Coming Soon properties will stay within the MLS.

Can I email my clients information about properties that are Coming Soon?

Yes. If you have auto-email searches set up, you can also go back and amend the searches to include properties with that status.

Will a Coming Soon status impact Days on Market once the property is Active?

No. Coming Soon will not accrue days on the counter for DOM or CDOM.

Is the Coming Soon status mandatory?

No. Listing the property under the Coming Soon status is a decision that should be made between you and the seller.

Do I need to have a listing agreement in place before placing a property in a Coming Soon status?

Yes. You must have a signed agreement in place before listing the property in the MLS. You must have written authorization from the seller to place information about the property on the MLS.

How do I assign a listing a Coming Soon status?

Begin by inputting the listing like you would any other and select Coming Soon as the status. Certain information is required, like expiration date, location, property type, etc. It’s a good idea to be as complete as possible so you can ensure your early marketing efforts are attracting the right buyers and to save time when you do change the status to Active.

Can I add Coming Soon status properties to my hot sheets?

Absolutely! There are already a lot of listings taking advantage of the new status. Customize your searches to include this option.

If a listing expired before it sold, can a Coming Soon status be used to relist the property?

If the property was listed as Coming Soon in the past 12 months, it cannot be relisted with the status again, even if the previous listing agreement has expired.


Effect of passive smoking on ciliary regeneration of nasal mucosa after functional endoscopic sinus surgery in children.
Passive smoking in the paediatric age group is associated with an increased frequency of a number of childhood respiratory disorders. However, its effect on ciliary regeneration after functional endoscopic sinus surgery for chronic sinusitis has not previously been reported. We conducted a prospective, nonrandomised cohort study on 38 paediatric patients with chronic sinusitis. We compared two patient groups--passive smokers and those not subjected to passive smoking--as regards ciliary regeneration after functional endoscopic sinus surgery, using objective methodology. We found passive smoking to have a negative impact on sinus cilia regeneration following functional endoscopic sinus surgery.


Prices Bytes

Inflation Slows Further In July CPI

August 11, 2017 (Prices Byte)

By Dean Baker

It appears rental inflation is slowing, rising at a 2.7 percent annual rate in the last three months.

It appears that inflation is continuing to decelerate in spite of an unemployment rate that is at a 16-year low. The overall and core CPI both rose 0.1 percent in July. This brings the rate of increase over the last 12 months in both measures respectively to 1.7 percent, well below the Fed’s 2.0 percent, as measured by the PCE, which translates into roughly a 2.2 percent CPI inflation rate.

Perhaps even more important than the level is the direction of change. The rate of inflation appears to be slowing. Taking the average price level over the last three months (May, June, and July) compared with the prior three months (February, March, and April), the annual rate of inflation in the core index has been just 0.7 percent. Even this modest increase is driven entirely by rising rents. If shelter costs are pulled out of the core index, it has been dropping at a 0.7 percent annual rate over the last three months compared with the prior three.

There is even some good news on rental costs. It appears that the rate of increase in rents is now slowing. The year-over-year increase for the owners’ equivalent rent (OER) component had been as high as 3.6 percent back in December. It is down to 3.2 percent for July and the annualized rate comparing the last three months with the prior three months is just 2.7 percent. (The OER is a better measure of actual housing costs because the rent proper index also includes some utilities.)

Inflation in almost all other components remains well contained. The price of medical care services increased by 0.3 percent in July and is up 2.3 percent for the last year. College tuition costs rose by just 0.1 percent in July and are up by 2.0 percent over the last year.

An exception is medical care commodities, which were up 1.0 percent in July and are now up by 3.7 percent over the last year. This is being driven by higher prices for prescription drugs, the index for which rose 1.3 percent in July and is now up by 4.2 percent over its year-ago level.

One area of notable price declines is used and new vehicles. The price of both fell by 0.5 percent in July. Over the last year, new vehicle prices are down 0.6 percent, while used vehicle prices have fallen by 4.1 percent. A big part of this story is a glut on the used car market due to the repossession of large numbers of cars sold on subprime loans. This depresses prices in the used car market, which then puts downward pressure on prices in the new car market.

Since the start of 2010, new vehicle prices have risen at less than a 1.0 percent annual rate, while used car prices have fallen by more than 4.0 percent. It’s worth noting the new vehicle index may not reflect actual sales prices. The Bureau of Labor Statistics (BLS) incorporates quality adjustments in its measurements. This means that its index for vehicle prices may be flat or declining, even if the price of a new car in 2017 is higher than the price in 2016. If people don’t perceive the quality improvements in the same way as BLS, they could still think car prices are rising.

This is one reason why concerns over a deflationary spiral are silly. Deflation could mean modest increases in the price of most goods, coupled with substantial quality improvements. It’s hard to envision the economy collapsing because the quality of goods and services is improving more rapidly.

In addition to the CPI report released today, yesterday’s report on the Producer Price Index also gives no indication of accelerating inflation. The overall final demand index fell 0.1 percent in July, while the core index excluding food, energy, and trade were flat for the month. Both indexes are up 1.9 percent over the last year. The intermediate goods index fell 0.1 percent, while the core intermediate goods index fell 0.3 percent.

In short, the July data suggest that inflation is likely slowing from its rate earlier in 2017. It is certainly not increasing.


Q:

Why does the native SIP stack included in Android 2.3 does not work over 3g?

I was wondering why does the native SIP stack included in the Android framework(since 2.3) does not work over 3g?
Could it have something to do with any laws or restrictions google may have with his partners?
And furthermore, does anybody know if there is any plans to remove that restriction ?
Thx

A:

In GingerBread, SipManager is set to work only on wifi.
`<bool name="config_sip_wifi_only">true</bool>`

But from 4.0 onwards, this config has been changed to false
So Ideally native sip stack should work on 3G from Ice Cream Sandwich onwards.
But again if the phone is sold by a service provider, then this might have been disabled. So phones sold unlocked may have this intact.
To check whether Sip over 3G is supported you can use the api
   SipManager.isSipWifiOnly(mContext);


14 Related Articles from 2018-11-18

500 'safety events' at Faslane nuclear submarine base. Figures show an increase in recorded incidents in recent years, with 80 in 2016 and 73 last year. >>

Abandoned dog found guarding neighbor's home after Camp Fire. A courageous border collie left to fend for herself in the deadly Camp Fire was found protecting the only home still standing on her block in Paradise. >>

Alex Trebek reveals the 'Jeopardy!' contestants that irk him. If you want to stay on Alex Trebek's good side, try not to do this on "Jeopardy!" >>

Diddy mourns for Kim Porter, says ‘more than soul mates’. Sean “Diddy” Combs is making his first public statements since the loss of longtime former girlfriend and mother of three of his children Kim Porter, saying they were “more than best friends,” and “more than soul mates.” >>

Diddy pays tribute to his 'soulmate' Kim Porter in touching post: 'I miss you so much'. Diddy breaks his silence on model Kim Porter, mother of three of his children, calling the days since his ex-girlfriend's sudden death a "nightmare." >>

Diddy writes 'I don’t know what I’m going to do without you baby' about late ex Kim Porter. Sean 'Diddy' Combs is speaking out over the tragic death of his ex Kim Porter. >>

Don't overlook this opportunity in your 401(k). More companies are adding a Roth option to their 401(k) to let workers stash after-tax dollars for retirement. Here's what you need to know to take advantage. >>

Hosting a potluck Friendsgiving? Here are the dos and don’ts. There are a few rules to follow when planning a potluck Friendsgiving. >>

How local reporters are covering the Camp Fire. Ten staffers at the Chico Enterprise-Record have lost their homes in the Camp Fire disaster. The newspaper's editor, David Little, says the staff feels "really helpless," but they are helping by informing the community. Papers are being delivered to evacuation centers and other locations. >>