V Lapoux
email: vlapoux@cea.fr

N Alamanos

F Auger

Y Blumenfeld

J-M Casandjian

M Chartier

M.D Cortina - Gil

V Fékou-Youmbi

A Gillibert

M Mac Cormick

F Maréchal

F Marie

W Mittig

F De

Oliveira Santos

N A Orr

A N Ostrowski

S Ottini-Hustache

P Roussel-Chomaz

J-A Scarpaci

J-L Sida

T Suomijärvi

J S Winfield

Virtual Coupling Potential for elastic scattering of 10,11 Be on proton and carbon targets

Keywords: 10, 11 Be(p, p), ( 12 C, 12 C), virtual coupling potential, weakly-bound nuclei PACS: 24.10.-i, 25.60.-t, 25.60.Bx, 25.40.Cm

The 10,11 Be(p,p) and ( 12 C, 12 C) reactions were analyzed to determine the influence of the weak binding energies of exotic nuclei on their interaction potential. The elastic cross sections were measured at GANIL in inverse kinematics using radioactive 10,11 Be beams produced at energies of 39.1 A and 38.4A MeV. The elastic proton scattering data were analyzed within the framework of the microscopic Jeukenne-Lejeune-Mahaux (JLM) nucleon-nucleus potential. The angular distributions are found to be best reproduced by reducing the real part of the microscopic optical potential, as a consequence of the coupling to the continuum. These effects modify deeply the elastic potential. Including the Virtual Coupling Potential (VCP), we show the ability of the general optical potentials to reproduce the data for scattering of unstable nuclei, using realistic densities. Finally, the concepts needed to develop a more general and microscopic approach of the VCP are discussed.

Light neutron-rich exotic nuclei are characterized by weak binding energies. They may develop peculiar structures like neutron-skin or halo structures. For instance, 6 He and 11 Be develop two-neutron and one-neutron halo, respectively. Another important effect is the couplings to the continuum states. The probability to be excited to continuum states is higher, compared to the stable isotopes, and this may induce new features in the interaction potential. The coupling to the other reaction processes may also be stronger. In principle, to calculate the interaction potential for elastic scattering, one should include all possible virtual couplings between the ground and higher excited states. These processes remove flux from the elastic channel. This effect is negligible for most stable nuclei, but becomes significant for weakly-bound nuclei [1]. The interaction term arising from couplings to inelastic channels is called the dynamical polarization potential (DPP) [1]. This term is complex, non-local and energy-dependent, it includes the coupling to excited states, the coupling to continuum states or to other reaction processes, like transfer reactions or break-up. We find it more appropriate to rename it as "virtual coupling potential" (VCP). The general formalism for such coupling processes in the interaction potential is described in Feshbach's theory [2]. But its exact calculation would require the precise knowledge of the spectroscopy of the nucleus and the transition strengths to bound and continuum excited states. Due to the difficulty to evaluate these interaction couplings, they are not taken into account a priori in the usual optical model approaches. However, in the case of a weakly-bound nucleus like 6 Li (S alpha+d = 1.46 MeV) easily described as a two-body nucleus, it was possible to describe microscopically the continuum states and to deduce the effect due to the coupling potential [3] in the elastic scattering of 6 Li on various targets. It was shown [1,3] that the coupling effects were responsible for the reduction of the real part of the potential needed to reproduce the elastic data in the framework of the folding model [4]. For exotic isotopes with lower particle thresholds, the coupling between the ground state and the continuum is expected to increase. Our aim is to investigate the effect of the weak binding of exotic nuclei on the elastic scattering data to test the validity of the effective nucleon-nucleon N N interactions used for the reaction analysis, and to know whether the weak binding of exotic nuclei should appreciably enhance the VCP. Finally we want to determine a general form of this potential. In [5], the 6 He(p,p) elastic scattering data at 38.3 A.MeV were analyzed using the microscopic JLM potential [6]. It was shown [5] that the angular distributions of 6 He on proton are better reproduced with a reduction of the real part of the microscopic optical potential rather than with an enhancement of the imaginary part. The wide angular range of the angular distributions (up to 71.5 • c.m.) allowed us to draw this conclusion. This effect was attributed to the continuum couplings. A phenomenological VCP was simulated. The same effect was found in the elastic scattering 6 He+ 12 C [7]. The enhancement and the role of the continuum couplings in the case of the weakly-bound radioactive nucleus 6 He on proton target have been emphasized in [8] and the polarization potential was deduced microscopically from the inversion of the S-matrix in the framework of the Coupled Discretized Continuum Channels (CDCC) calculations.

Elastic data are well reproduced when the coupling effect is taken into account, as done, for instance, within the CDCC calculations, including some cluster structure or introducing a phenomenological VCP. Through the analysis of such data we can understand how the cross sections are affected by the coupling effects and it is possible to deduce the optical potentials required to describe the direct reactions; afterwards, we can check the validity of the microscopic densities tested in the reaction analysis. A similar analysis was carried out for the neutron-deficient 10,11 C [9]. In the case of the elastic scattering 8 He+p [10], we found that it was necessary to take into account the coupling to the (p,d) reaction within the coupled-reaction framework. It was shown that the important modification of the potential needed to reproduce the elastic scattering was due to the loss of flux in the one-neutron transfer reaction. In this case, the VCP was mainly produced by the (p,d) coupling effect. A set of elastic data of light nuclei on protons, including 10,11 Be, was presented and analyzed in Ref. [11]. The data were well reproduced using global or microscopic proton-nucleus potentials provided that the real part was reduced or the imaginary part enhanced. However, the data did not extend to large enough angles to choose between the two possibilities. This article presents new elastic scattering data of 10,11 Be on proton and carbon targets, collected at the GANIL (Grand Accélérateur National d'Ions Lourds, Caen, France). The angular distributions were measured at energies close to 40A MeV up to 70 • in the center of mass (c.m.) frame for proton scattering, and up to 20 • c.m for scattering on carbon. The data were collected on a wide angular domain to investigate the VCP effect. The article explains the analysis carried out to discuss the coupling effects induced by 10,11 Be.

We first present our measurement. The analysis of the proton-nucleus elastic data is discussed, the VCP is introduced, and its effect is shown on the pnucleus data. The data for 10,11 Be on carbon target are then compared to the folding model calculations and the influence of the VCP is explained. In conclusion, we discuss the general framework needed to develop a microscopic analysis of the VCP.

The experiment was carried out at the GANIL coupled cyclotron facility. The 10,11 Be secondary beams were produced by fragmentation of a 75 MeV/nucleon primary 18 O beam on a carbon production target located between the two superconducting solenoids of the SISSI device [START_REF] Joubert | Particle Accelerator Conference IEEE[END_REF]. The secondary beams were purified with an achromatic degrader set in the beam analysis spectrometer. The 10,11 Be beams were obtained at energies of 39.1A and 38.4A MeV, with intensities of the order 10 5 pps and 3.10 4 pps, respectively. They were scattered from a 10 mg/cm 2 thick polypropylene target (density of 0.896 g/cm 3 ). Elastic angulardependent cross sections of 10,11 Be projectiles on protons and carbon nuclei were measured with the SPEG spectrometer [START_REF] Bianchi | [END_REF]. The scattered particles were identified at the focal plane by the energy loss measured in an ionisation chamber and the residual energy measured in a thick plastic scintillator. The momentum and the angle after the target were obtained by track reconstruction of the trajectories determined by two drift chambers straddling the focal plane of the spectrometer. Position and angle of the projectiles on the target were determined event by event by two beam detectors. The experimental set-up is similar to the one described in [5,7] for the case of 6 He on protons and 12 C. With the polypropylene reaction target containing both hydrogen and carbon nuclei, we obtained a simultaneous measurement of the cross sections on protons and 12 C. The laboratory angle range covered was from 1.3 • to 8.5 • . The good energy resolution of the SPEG spectrometer ( ∆E E = 10 -3 ) allowed us to extract the elastic scattering data on 12 C without any contamination from scattering to the 12 C excited states. Cross sections on 12 C are dominated at small angles by Coulomb deflection, so the calculation at these angles is not sensitive to the nuclear potential. Consequently, for this angular range, all calculations lead to the same first maximum in the angular distribution, thus providing an absolute normalization for the data on 12 C, and as a result on the protons. 12 C and 10 Be have a first excited state (2 + ) at 4.44 and 3.37 MeV, respectively. With the good energy resolution of the SPEG, it was possible to separate elastic scattering of 10 Be on carbon from inelastic contributions. This is not the case for 11 Be for which the energy of the first excited state 1/2 - is at 320 keV, very close to the 1/2 + ground state.

With the ECIS code [START_REF]ECIS97 code[END_REF], we did coupledchannel calculations to estimate the relative yields of the elastic cross sections versus inelastic ones to the 1/2 -for 11 Be on p and 12 C targets. Phenomenological potentials were employed, and also the known large value for B(E1, 1/2 + gs → 1/2 -)(=0.116 e 2 .fm 2 [START_REF] Millener | [END_REF]16]). This analysis showed that the inelastic cross sections are at least two orders of magnitude lower than the corresponding elastic cross sections in the angular domain of interest and can be neglected. Higher excitation energy states in 11 Be are not bound against neutron emission (S n = 504 keV) and cannot contribute in the 11 Be yield detected in the focal plane of the spectrometer. The data for the elastic scattering of 10,11 Be on protons are presented in Figs. 12. The angular resolution is of the order of 0.5 • in the laboratory system giving errors in the c.m. system of 10 Be+p and 11 Be+p of 5.5 • and 6 • , respectively. For 10 Be+ 12 C ( 11 Be) , the angular resolution is 0.95 • c.m.

(1 • c.m. ). In the figures, the error bars are statistical and the angular bins correspond to the resolution.

The idea in this article was to examine the validity or limitation of the existing well-established models for the nuclear potential, when we deal with weaklybound nuclei. In this case, we have to take care about effects which occur at the nuclear surface. It means that coupling effects must be incorporated, whatever the choice made on the N N potential for the folding procedure. Here, we have chosen the effective JLM potential for p+Be and the folding potential for Be+ 12 C with the effective N N interaction CDM3Y6, and from the arguments developed below the potentials of our analysis are fully consistent.

We first want to examine the validity of the microscopic nucleus-nucleon potential for the description of the proton elastic scattering on exotic nuclei. The nucleus-nucleon elastic scattering can be described with the complex nucleon-nucleon interaction JLM [6] deduced from calculations in infinite symmetric nuclear matter with the local density approximation, and for energies up to 160 MeV. This model generates a complex microscopic potential which only depends on the scattering energy and on the density of the involved nucleus. The potential is written : U JLM = λ V V + iλ W W , with λ V , λ W the normalization factors of the real V and imaginary W parts of the potential. In the case of stable nuclei, it reproduces successfully a large range of proton and neutron elastic scattering angular dis-tributions, without any free parameter [17]. In the case of light exotic nuclei, data are well reproduced, provided the imaginary potential be somewhat adjusted by a normalization factor λ W ∼ 0.8 [18]. The elastic JLM potentials for 10,11 Be+p are calculated using the Hartree-Fock (HF) densities described in Ref. [19]. We consider these densities as realistic ones, since the HF calculations were constrained so as to reproduce the neutron separation energies and the matter root mean square (rms) values of these densities are found consistent with the empirical matter rms values deduced from reaction cross sections data. The rms radii of the nuclear proton, neutron, matter, distributions for 10,11 Be are r m =2.44 [r p = 2.26, r n = 2.56] fm and 2.92 fm [r p = 2.27, r n = 3.24], respectively. In the c.m. angular range from 20 • to 40 • , there is a large discrepancy between the standard JLM curve (λ V =1 and λ W =0.8) and the data. To improve the agreement with the data, we tried two approaches, either the reduction of the real part, searching for the best λ V < 1 value (and keeping λ W = 0.8) or the enhancement of the absorption with the increase of the imaginary potential λ W > 1 (keeping λ V = 1). The curves obtained with these prescriptions are displayed in Figs. 12. With this procedure, the best agreement with the 10 Be data in the angular domain between 20 and 40 • is obtained when λ V =0.9, (with fixed λ W = 0.8) or with λ W =1.2, (fixed λ V = 1). For 11 Be, the values of the normalization factors are λ V =0.75 (fixed λ W = 0.8) and λ W = 1.4 (fixed λ V = 1). As found for 6 He [5] the angular distributions for 11 Be are better reproduced on the whole angular range when the real part of the JLM potential is scaled down. The origin of this effect can be attributed to the VCP. In Ref. [5], the 6 He + p scattering data were reproduced using a phenomenological VCP. Such a potential is a repulsive surface potential, which can produce, in the surface region of the nucleus+target system, a similar effect as the reduction of the real part of the potential. This leads to the global decrease of the cross sections in the angular region from 20 to 40 • c.m. , consistent with the data. Similarly, to reproduce the 11 Be + p data, we could use such a phenomenological VCP but, as can be seen in Fig. 2, the simple reduction of the real potential is enough to simulate the effects of the VCP for 11 Be. This may be attributed to the fact that 11 Be displays similar features, as the ones of 6 He : a low S n and the main coupling effects are the coupling to low-lying unbound and continuum states. In con-strast, for 10 Be, the neutron threshold S n is higher, at 6.8122 MeV and the main coupling effect could possibly be found in the one-neutron transfer (p,d) or even in the (p,t) reaction. Consequently, a good description of the 10 Be+p data would require to go beyond our simple VCP modeling and to investigate carefully the influence of the coupled reaction channels on the elastic scattering. This will be the subject of a further work. For the elastic scattering on the 12 C target, the ratio of cross sections in the c.m. frame over the Rutherford cross sections are plotted in Figs. 34. The binning of the data corresponds to the angular resolution in the c.m. frame. We carry out the same analysis as done successfully in the case of the 6 He+ 12 C data [7]. For this system, it was possible to explain the coupling effects induced by the halo-nucleus 6 He using the folding model and a phenomenological VCP in the coupled channel framework. The cross sections are calculated using the ECIS97 code [START_REF]ECIS97 code[END_REF]. The real potentials U F of 10 Be+ 12 C and 11 Be+ 12 C are calculated within the framework of the folding model: the potential is obtained by double-folding over the nuclear matter densities of the projectile and target nuclei with the density-dependent N N interaction CDM3Y6 (Paris-form) [20]. The nuclear density of 12 C is a 2-parameter Fermi function with radius R = 2.1545 fm, diffuseness a = 0.425 fm, r m = 2.298 fm [21] which is consistent with the experimentally known charge density. In a first step, we only use the real folding potential and a phenomenological imaginary potential W , which is a Woods-Saxon function parametrized as in Ref. [START_REF] Broglia | Heavy Ions Reactions[END_REF] with depth W I , reduced radius r I (r I =R I /(A

1/3 P + A 1/3
T ), A P and A T the mass numbers of projectile and target), and diffuseness a I . These parameters are given in Tab. 1. With the interaction potential defined as U F + iW , the data are not reproduced as shown in Figs. 3-4. As in [5,7], we introduce a phenomenological VCP which is a complex repulsive surface potential simulating the coupling effects. U V CP is complex with the real part V V CP (and similarly imaginary one W V CP ) written as :

V V CP = -4 * V vcp x r [1 + x r ] 2 (1)
with x r = exp r-Rvcp avcp

. We have V vcp ≤ 0 which gives a repulsive potential. For simplicity, the VCP is written with no radius (R vcp = 0 fm). The total interaction potential is now defined as U F + iW + U V CP and we adjust the parameters of U V CP in order to reproduce the data. The best agreement obtained is presented with the solid lines in Figs. 34. The parameters of U V CP are given in Table 1. This analysis is only a simple model, built in order to exhibit the coupling effects and to propose a simple shape of VCP. A more sophisticated analysis could be undertaken using the coupled reaction framework to explore its origin.

Several theories were developed to have a deeper understanding of the continuum effects : for highenergy reaction studies (few 100A MeV) the role of the continuum coupling has been addressed in several few-body approaches, by implicitly including the coupling to all orders [23][24][25]. In the study of reaction mechanisms at lower energy (few 10A MeV), the coupling effects have been taken into account by explicitly coupling to a discretized continuum [3,26]. More generally, for the analysis of the one nucleontransfer reactions and elastic scattering on light targets like deuteron targets, a coupled-reaction framework [27] is needed. A complete study of the 10,11 Be scattering would require a precise treatment of the VCP through an explicit calculation of the coupling, as done for instance with the CDCC methods [10]. We should take into account not only the coupling to the one-neutron (p,d) reaction but also to the inelastic scattering. Such work will benefit from the last developments of the nuclear reaction models including the core excitation [28].

In conclusion, our analysis is a first approach to deduce the main features of the VCP for 10,11 Be. The elastic scattering of exotic nuclei 10,11 Be was calculated using the optical model and a microscopic approach for the proton-nucleus potential, and for the nucleus-12 C real potential. Densities taking into account the large extension of these neutron-rich nuclei were included. We found that the elastic scattering data of the exotic nucleus 11 Be on a proton is well described with a simple reduction of the real part of the JLM potential. This reduction is able to simulate the coupling effects induced by the weakly-bound projectile. For the analysis of the elastic scattering on carbon target, the coupling effect was introduced explicitly through the parameterization of a VCP. More generally, to reach an accurate and improved description of the direct reactions with radioactive nuclei, we will have to calculate explicitly the VCP by including the couplings to the excited states, the continuum states and to reaction channels like (p,d) reaction. -5 1.68 Table 1 Parameters of the imaginary part W of the optical potential and of the VCP for 10,11 Be on carbon target.

2 Fig. 1 .

 21 Fig.1. Cross sections for the10 Be + p elastic scattering at 39.1A MeV compared to calculations using the JLM potential and the "Sagawa" density. The full circles correspond to the data. The dashed line corresponds to the standard JLM calculation for light nuclei. Full line (respectively dotted line) corresponds to calculations in which the real part (imaginary) was renormalized.

4 Fig. 2 .

 42 Fig. 2. Same as in Fig. 1 for the 11 Be + p elastic scattering at 38.4A MeV. [28] N.C. Summers, F.M. Nunes and I.J. Thompson, Phys Rev C 73, 031603 (2006).

Fig. 3 .

 3 Fig.3. Cross sections for the 10 Be +12 C elastic scattering at 39.1A MeV are compared with calculations using the CDM3Y6 folding potential and the imaginary potential W (dashed line). Data are better reproduced taking into account a complex VCP U V CP (solid line), given in the text.

Fig. 4 . 6 11

 46 Fig. 4. Same as in Fig. 3 for 11 Be at 38.4A MeV.

Acknowledgments

We thank Dr H. Sagawa, for the 10,11 Be density distributions, and Dr. Dao T. Khoa for his folding code, DFPD2. The assistance of the SPEG crew, P. Gangnant and J.-F. Libin, in the preparation and running of the experiment is gratefully acknowledged.


Gautam K Das

Guilherme D Da Fonseca
email: guilherme.diasdafonseca@udamail.fr

Ramesh K Jallu

Efficient Independent Set Approximation in Unit Disk Graphs *

Keywords: Maximum Independent Set, Unit Disk Graph, Approximation Algorithms, Polynomial Time Approximation Scheme

We consider the maximum (weight) independent set problem in unit disk graphs. The high complexity of the existing polynomial-time approximation schemes motivated the development of faster constant-approximation algorithms. In this article, we present a 2.16-approximation algorithm that runs in O(n log 2 n) time and a 2approximation algorithm that runs in O(n 2 log n) time for the unweighted version of the problem. In the weighted version, the running times increase by an O(log n) factor. Our algorithms are based on a classic strip decomposition, but we improve over previous algorithms by efficiently using geometric data structures. We also propose a PTAS for the unweighted version.

Introduction

Given a set P of n points in the plane, a unit disk graph (UDG) has vertices P and an edge pq corresponds to a pair of points p, q ∈ P, if pq ≤ 1, where pq denotes the Euclidean distance between p and q. Equivalently, a unit disk graph is the intersection graph of disks of unit diameter centered at the points in P. In this geometric setting, an independent set consists of a subset of P with minimum distance greater than 1. In the unweighted version, a maximum independent set (MIS) is an independent set of maximum cardinality. In the weighted version, we are given a weight function w : P → R + and we want to find a maximum weight independent set (MWIS), that is, an independent set that maximizes the sum of the weights of its points. The M(W)IS problem is well studied due to its wide range of applications, including but not limited to map labeling, clustering, wireless ad-hoc networks, and coding theory.

The MIS problem on UDGs is known to be NP-hard [START_REF] Clark | Unit disk graphs[END_REF]. There are polynomialtime approximation schemes (PTASs) for several optimization problems on unit disk graphs [START_REF] Cheng | A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks[END_REF][START_REF] Das | Approximation algorithms for maximum independent set of a unit disk graph[END_REF][START_REF] Hochbaum | Approximation schemes for covering and packing problems in image process[END_REF][START_REF] Hunt | NC-approximation schemes for NP-and PSPACE-hard problems for geometric graphs[END_REF][START_REF] Matsui | Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs[END_REF][START_REF] Nieberg | Approximation schemes for wireless networks[END_REF], including maximum (weight) independent set. However, the high complexities of the PTASs motivated the recent study of faster constantapproximation algorithms, notably for minimum dominating set [START_REF] Carmi | Minimum dominating set problem for unit disks revisited[END_REF][START_REF] Da Fonseca | Efficient sub-5 approximations for minimum dominating sets in unit disk graphs[END_REF][START_REF] Da Fonseca | Lineartime approximation algorithms for geometric intersection graphs[END_REF][START_REF] De | Approximation algorithms for a variant of disc. piercing set problem for unit disks[END_REF] and maximum (weight) independent set [START_REF] Da Fonseca | Lineartime approximation algorithms for geometric intersection graphs[END_REF][START_REF] Das | Approximation algorithms for maximum independent set of a unit disk graph[END_REF].

The history of constant-approximation algorithms for M(W)IS in unit disk graphs is rich. We begin by reviewing some constant-approximation algorithms. The following algorithms receive the point coordinates as input and execute on the Real RAM and the O(n)-time algorithms use constant-time hashing and floor function (otherwise, their running times increase to O(n log n)).

In their seminal work, Marathe et al. [START_REF] Marathe | Simple heuristics for unit disk graphs[END_REF] presented greedy algorithms which attain a 3-approximation algorithm for the unweighted version, and a 5-approximation for the weighted version. Using efficient data structures, their algorithms can be implemented to run in O(n) time. Using a strip decompositon, Matsui [START_REF] Matsui | Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs[END_REF] presented an O(n 2 )-time algorithm with approximation ratio (1 + (2/ √ 3) + ε) < 2.16 for the weighted version. A different strip decomposition yields an O(n 3 )-time 2-approximation algorithm for the weighted version [START_REF] Das | Approximation algorithms for maximum independent set of a unit disk graph[END_REF]. The use of coresets give an O(n)-time (4 + ε)-approximation algorithm for the weighted version [START_REF] Da Fonseca | Lineartime approximation algorithms for geometric intersection graphs[END_REF].

Decomposing the problem into strips and using the shifting strategy [START_REF] Hochbaum | Approximation schemes for covering and packing problems in image process[END_REF], Matsui [START_REF] Matsui | Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs[END_REF] proposed the first PTAS for the problem. For any positive integer k ≥ 2, it gives a solution of weight at least (1

-1/k)OP T in O(n 4 2(k-1)/ √ 3
) time, where OP T is the weight of an optimal solution. For any positive integer k > 1, another PTAS based on a similar strategy [START_REF] Das | Approximation algorithms for maximum independent set of a unit disk graph[END_REF] gives a ((1

+ 1 k ) 2 )-approximation in O(n σ k log k ) time and O(n) space, where σ k ≤ 7k 3 + 2.
The complexity of the PTASs [START_REF] Hunt | NC-approximation schemes for NP-and PSPACE-hard problems for geometric graphs[END_REF][START_REF] Nieberg | Approximation schemes for wireless networks[END_REF] based on different strategies tend to be even higher.

The problem is also studied in the context of fixed parameter tractable algorithms. Van Leeuwen [START_REF] Van Leeuwen | Approximation algorithms for unit disk graphs[END_REF] proposed a fixed parameter tractable algorithm which runs in O(t 2 2 2t n) time, where the parameter t is called the thickness of the UDG. A UDG is said to have thickness t, if each strip in the slab decomposition (of width 1) of the UDG contains at most t disk centers.

The study of independent sets in geometric intersection graphs is not limited to UDGs, but studied also for other objects such as rectangles, pseudo disks, etc. For a given set R of rectangles of fixed size, Agarwal et al. [START_REF] Agarwal | Label placement by maximum independent set in rectangles[END_REF] proposed a 2-factor approximation algorithm for the MIS problem that runs in O(n log n) time, as well as a PTAS. For a given set of arbitrary rectangles of bounded aspect ratio (or, more generally arbitrary fat convex bodies) in R d , Chan [START_REF] Chan | Polynomial-time approximation schemes for packing and piercing fat objects[END_REF] proposed a PTAS that computes an (1 + ε)-approximation in O(n O(1/ε d-1 ) ) time and space. Chan et al. [START_REF] Chan | Approximation algorithms for maximum independent set of pseudo-disks[END_REF] considered the same problem for pseudo disks in the plane.

Our results

In this paper, we present four new approximation algorithms that improve the best running time for the same approximation ratios. Table 1 summarizes the constant-approximation algorithms for the problem, including our results. Next, we describe the techniques that allowed such improvements. We also present a PTAS for the unweighted version.

Given two real numbers h and r, a strip of width h rooted at r is the unbounded planar

O(n) O(n) [20] 4 + ε O(n) O(n) [13] 2.16 O(n log 2 n) O(n) Sec. 3 2.16 O(n log 3 n) O(n log n) Sec. 3 2 O(n 2 log n) O(n 2 ) Sec. 4 2 O(n 2 log 2 n) O(n 2 log n) Sec. 4
Table 1: Approximation ratios and complexities of several constant-approximation algorithms for maximum (weight) independent set in unit disk graphs.

region R × [r, r + h]. The algorithms from [START_REF] Das | Approximation algorithms for maximum independent set of a unit disk graph[END_REF][START_REF] Matsui | Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs[END_REF] are based on a procedure to solve the problem optimally when all points lie inside a sufficiently small strip. Strips of width √ 3/2 are used in the 2.16-approximation algorithm [START_REF] Matsui | Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs[END_REF], while strips of width 1 are used in the 2-approximation algorithm [START_REF] Das | Approximation algorithms for maximum independent set of a unit disk graph[END_REF]. The algorithms presented in this paper are based on the same strategy and strip widths. However, several geometric data structures are used to speed-up the algorithms. The data structures we use are presented in Section 2, followed by the 2.16-approximation algorithm in Section 3, and the 2-approximation algorithm in Section 4. The proposed PTAS is discussed in Section 5.

Data Structures

Given a set P of n data points in d-dimensional space, an emptiness query consists of determining whether a given query range R contains no data point, that is, whether P ∩ R = ∅, returning an arbitrary point in P ∩ R if it exists. A maximum query is defined similarly, but the data points have real weights and the query finds a point of maximum weight in P ∩ R if it exists. In an anti-disk query, the range R is the complement of a disk of arbitrary radius r centered at q, that is, the region formed by all points with Euclidean distance greater than r from q.

Maximum queries reduce to emptiness queries as follows. As far as we know, this reduction has never been published, but it is likely that other researchers independently noticed the same construction.

Lemma 2.1. Consider a set of n data points with weights and a query range. A data structure for answering emptiness queries with storage S(n) = Ω(n), preprocessing time B(n) = Ω(n), and query time Q(n) yields a data structure for answering maximum queries for the same range with preprocessing time

O(B(n) log n), query time O(Q(n) log n), and storage O(S(n) log n).
Proof. We assume that all weights are distinct, otherwise we break the ties arbitrarily. We build a binary tree where each node contains a data structure for emptiness queries as follows. The root contains the emptiness data structure for all data points. Consider a node which stores the data structure for a set of points P. Let µ be the median weight among the points in P. The left subtree is defined recursively for the points in P with weight at most µ, and the right subtree is defined analogously for the remaining points of P. The recursion stops when P has only 1 point.

Notice that the tree has lg n + 1 levels, and exactly n data points at each level. The total storage is therefore

S (n) = lg n +1 =0 2 S n 2 ≤ lg n +1 =0 S(n) = O(S(n) log n),
where the first inequality uses that S(n) = Ω(n). The preprocessing time is calculated the same way.

To answer a maximum query, we verify at the root node whether the query range is empty. If not, we verify if the query range is empty for the right subtree. If it is empty, we recurse on the left subtree. Otherwise, we recurse on the right subtree. The procedure ends when we reach a leaf. The leaf reached contains the point of maximum weight inside the query range, which we return. The bound on the query time follows from the fact that we performed O(log n) emptiness queries, one per level of the tree.

The previous lemma deserves two remarks. (i) It follows from the proof that the log n factors in the storage, preprocessing time, and query time disappear if the respective complexities are Ω(n 1+ε ), Ω(n 1+ε ), and Ω(n ε ). (ii) Using known data structures for halfspace emptiness queries such as [START_REF] Chan | Optimal partition trees[END_REF][START_REF] Matoušek | Reporting points in halfspaces[END_REF], we beat the lower bounds in [START_REF] Arya | Tight lower bounds for halfspace range searching[END_REF][START_REF] Brönnimann | How hard is halfspace range searching[END_REF] for half-space maximum queries. This is possible because the set of generators depends on the point weights, which is forbidden by the semi-group arithmetic model in which the lower bounds are stated.

Many techniques yield efficient data structures for anti-disk emptiness searching. For example, one can use a farthest-point Voronoi diagram [START_REF] Berg | Computational Geometry: Algorithms and Applications[END_REF]Ch. 7] Sometimes, the reduction from Lemma 2.1 is an overkill, and a logarithmic factor can be avoided by a simpler approach.

Lemma 2.4. Given a set of n planar points with integer weights in {1, . . . , n}, there exists a data structure that answers anti-disk maximum queries in O((w maxw ret ) log n) time with O(n) storage and O(n log n) preprocessing time, where w max is the maximum weight among the points in the data structure and w ret is the weight of the point returned by the query, or 0 if the query is empty.

Proof. We keep an array of n data structures D 1 , . . . , D n from Lemma 2.2 where D i stores the points of weight i. To answer a query, we start from the maximum i that corresponds to a non-empty D i , decrementing i until the query returns non-empty. Analyzing the data structure is trivial.

A search problem is decomposable if for any set S and S ⊆ S, the answer to a query q(S) can be calculated in constant time from the results of q(S ) and q(S \ S ). The following Lemma is due to Overmars and Leeuwen [START_REF] Overmars | Worst-case optimal insertion and deletion methods for decomposable searching problems[END_REF] (see also [START_REF] Bentley | Decomposable searching problems I. static-to-dynamic transformation[END_REF]). The log n factor in the query and insertion times disappear if the query and preprocessing times are respectively Ω(n ε ) and Ω(n 1+ε ). Sometimes, dynamic data structures specifically designed for a particular problem are more efficient than the dynamized version, but this is not known to be the case for half-space emptiness. A specific data structure supporting insertions and deletions is presented in [START_REF] Chan | A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries[END_REF].

Combining Lemma 2.5 with Lemmas 2.3 and 2.4 we have the following lemmas.

Lemma 2.6. Given a set of n weighted planar points, there exists a semi-dynamic data structure that answers anti-disk maximum queries in O(log

Small strips

In this section, we present a 2.16-approximation algorithm for the maximum (weight) independent set problem on unit disk graphs. Recall that an unit disk graph is represented as a set P of n points where an edge pq corresponds to a pair of points p, q ∈ P with pq ≤ 1. We use x(p i ) and y(p i ) to represent the x and y coordinates respectively of p i ∈ P. In order to describe multiple results with a unified treatment, we assume that a weight function with w(p) = 1 for all p ∈ P is provided in the unweighted version. Our approximation algorithms uses a decomposition of the unit disk graph into strips.

The following lemma shows why determining the maximum independent set within a strip is useful for approximating the unrestricted problem. The proof is a simple application of the shifting strategy [START_REF] Hochbaum | Approximation schemes for covering and packing problems in image process[END_REF], paying attention to the fact that the width h must be a constant rational number for the proof to work (the running time depends on the denominator of h). Lemma 3.1. An exact algorithm for the maximum (weight) independent set for a set of m points inside a strip of rational width h with running time T (m) yields an approxilation algorithm for maximum (weight) independent set of n points in arbitrary locations with approximation ratio 1 + 1/h and running time O(T (n) + n log n).

Matsui [START_REF] Matsui | Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs[END_REF] showed that a unit disk graph inside a strip of width √ 3/2 is a cocomparability graph, and therefore the maximum weight independent set can be determined exactly in time linear on the size of the input graph [START_REF] Köhler | A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs[END_REF]. Since a complete graph is a unit disk graph within an arbitrarily small strip, building the graph takes quadratic time in the worst case. The crucial property shown by Matsui and used by our algorithm is the following. To obtain a logarithmic improvement for the unweighted version, we use an additional property of unit disk graphs from [START_REF] Marathe | Simple heuristics for unit disk graphs[END_REF]. The left neighborhood of a point p is the set of points q with pq ≤ 1 and x(q) ≤ x(p).

Lemma 3.3. The left neighborhood of a point p has at most 3 independent vertices.

Let Q = {p 1 , p 2 , . . . , p m } be the set of points lying in a strip H with p 1 , p 2 , . . . , p m in increasing order of their x-coordinates. Given 1 ≤ i ≤ m, we define the set S i ⊆ Q is as follows: (i) S i is an independent set, (ii) p i is the rightmost point of S i , and (iii) S i is a maximum weight set satisfying the previous two properties. Let W i denote the sum of the weights of the points in S i . For simplicity, the sets S i can be viewed as x-monotone polygonal chains formed by connecting the points of S i from left to right (see Figure 1). The objective of our algorithm is to extend these chains as long as possible. A chain containing maximum number of points is reported.

H √ 3/2
Figure 1: Pictorial representation of the sets S i in the form of chains, with the maximum independent set marked.

Our algorithm uses dynamic programming to compute S i for i = 1, . . . , m as follows. We calculate S i using S j for j < i iteratively as S i = S j ∪ {p i } where j is the index < i that satisfies p i p > 1 and maximizes W . In case there is no point p , satisfying p i p > 1 and < i, the algorithm sets S i = {p i }. To efficiently determine the index j, we use the data structure from Lemma 2.6 (weighted) or 2.7 (unweighted). The pseudocode is presented in Algorithm 1. Proof. To see that S i is calculated correctly by the procedure, notice that by Lemma 3.2, p i p j > 1 for j < i implies that a point p k to the left of p j with p j p k > 1 satisfies p i p k > 1. By construction, S i contains p i and its weight is maximum.

To execute the algorithm in O(m log 3 m) time, we use the data structure for anti-disk maximum queries supporting insertions from Lemma 2.6 to store p j for j < i. The weight of p j in the data structure is W j . The O(m) insertions (line 10) and queries (line 7) take together O(m log 3 m) time, and the space is O(m log m) due to the storage of the data A = complement of a disk of radius 1 centered at p i 7:

j = maxQuery(D, A) Returns 0 if no point is found 8: S[i] = j Represents S i = S j ∪ {p i } with S 0 = ∅ 9: W [i] = W [j] + w(p i ) 10: insert(D, i, p i , W [i])
Insert point p i with label i and weight

W [i] into D 11: if W [i] > W [max] then 12: max = i 13:
end if 14: end for 15: i = max, IS = {} 16: while i = 0 do To reduce the running time to O(m log 2 m) for the unweighted version, we use the data structure from Lemma 2.7. In the unweighted version, W i = |S i | and therefore the weight W i is an integer between 1 and m. Let max be the index of the point of maximum weight in the data structure at the time when a point of index j is returned by the query. We use Lemma 3.3 to show that W max -W j ≤ 3. If |S max | ≤ 3, the statement follows trivially. Otherwise, let p a , p b , p c , p max be the four rightmost elements in S max from left to right. We have W max = 1 + W c = 2 + W b = 3 + W a . By Lemma 3.3, p a , p b , p c , p max cannot be all adjacent to p i , which shows that w maxw ret ≤ 3. Therefore, using the data structure from Lemma 2.7, the O(m) insertions and queries take together O(m log 2 m) time, and the space is O(m).

Combining Lemma 3.1 and Theorem 3.4, we obtain the following theorem.

Large Strips

In this section, we present a 2-approximation algorithm for the maximum (weight) independent set problem on unit disk graphs. The algorithm uses a decomposition of the region containing the disk centers into strips of width 1. Das et al. [START_REF] Das | Approximation algorithms for maximum independent set of a unit disk graph[END_REF] proved the following lemma which is similar to Lemma 3.2 for these larger strips. Let Q = {p 1 , p 2 , . . . , p m } be the set of points lying in the strip H with p 1 , p 2 , . . . , p m in increasing order of their x-coordinates. Given 1 ≤ j < i ≤ m with p i p j > 1, we define the set S i,j ⊆ Q as follows: (i) S i,j is an independent set, (ii) p j and p i are the two rightmost points of S i,j , and (iii) S i,j is a maximum weight set satisfying the previous two properties. Furthermore, we define S i,0 = {p i }.

Let W i,j denote the sum of the weights of the points in S i,j . Let S i = {S i,j | 1 ≤ j < i and p i p j > 1} denote the collections of sets S i,j for fixed i.

Our algorithm uses dynamic programming to compute S i,j for i = 2, . . . , m and j = 1, . . . , i -1 with p i p j > 1 as follows. We calculate S i,j using S j,k for k < j < i iteratively as S i,j = S j,k ∪ {p i } where k is the index < j maximizing W j, and satisfying the constraint that {p i , p j , p } is an independent set. In case there is no point p satisfying the previous constraint, the algorithm sets S i,j = {p i , p j }. To efficiently determine the index < j that satisfies the previous constraint and maximizes W we use an array of data structures D 1 , . . . , D m from Lemma 2.3 (weighted) or 2.4 (unweighted). The data structure D i stores a point p j with weight W i,j for each set S i,j ∈ S i . Note that the data structure D j only stores points p k such that p j p k > 1. The pseudo-code is presented in Algorithm 2. Proof. To see that S i,j calculated by the procedure is indeed an independent set, notice that by Lemma 4.1, {p i , p j , p k } be independent implies that a point p s to the left of p k with {p j , p k , p s } independent satisfies p i p s > 1. By construction, S i,j contains p i , p j as the points with maximum x coordinates and its weight is maximum.

To execute the algorithm in O(m 2 log 2 m) time, we use m data structures for antidisk maximum queries from Lemma 2.3. For each point p i , the data structure D i stores the point p j for each set S i,j ∈ S i . The weight associated with p j is W i,j . The data structure D i is static, preprocessed (line 26) with points collected in the set T

Lemma 2 . 5 .

 25 A static data structure for a composable problem storing n elements with preprocessing time B(n), query time Q(n), and storage S(n) yields a semi-dynamic data structure supporting insertions for the same problem with insertion time O(B(n) log n/n), query time O(Q(n) log n), and storage O(S(n) + log n).

Lemma 3 . 2 . 3 / 2 .

 3232 Let H be a strip of width √ Consider p a , p b , p c ∈ H with x(p a ) < x(p b ) < x(p c ). If p a p b > 1 and p b p c > 1, then p a p c > 1.

Theorem 3 . 4 .

 34 Algorithm 1 correctly computes a MWIS for the set Q = {p 1 , p 2 , . . . , p m } inside a strip of width √ 3/2 in O(m log 3 m) time using O(m log m) space. In the unweighted version, the complexities decrease to O(m log 2 m) time and O(m) space.

Algorithm 1

 1 Maximum (weight) independent set inside a strip of width √ 3/2 Input: The set Q of m points p 1 , . . . , p m ordered by x coordinate inside a strip of width √ 3/2. Output: A maximum weight independent set of Q. 1: D = data structure from Lemma 2.6 (weighted) or 2.7 (unweighted) 2: S = array [1 . . . m] of integers 3: W = array [0 . . . m] of reals (weighted) or integers (unweighted) 4: W [0] = 0, max = 1 5: for i = 1, . . . , m do 6:

17 :

 17 IS = IS ∪ {p i } 18: i = S[i] 19: end while 20: return IS structure. The algorithm stores S i as a linked list from right to left. Part of the linked lists are shared by different sets S i , forming a DAG.

Theorem 3 . 5 .

 35 Given a set P of n weighted points, we can compute an approximation to the maximum weight independent set in O(n log 3 n) time and O(n log n) space with approximation ratio (1 + (2/ √ 3) + ε) < 2.16. In the unweighted version, the complexities decrease to O(n log 2 n) time and O(n) space.

Lemma 4 . 1 .

 41 Let H be a strip of width 1. Consider p a , p b , p c , p d ∈ H with x(p a ) < x(p b ) < x(p c ) < x(p d ). If both {p a , p b , p c } and {p b , p c , p d } are independent sets, then p a p d > 1.

Theorem 4 . 2 .

 42 Algorithm 2 correctly computes a MWIS for the set Q = {p 1 , p 2 , . . . , p m } inside a strip of width 1 in O(m 2 log 2 m) time using O(m 2 log m) space. In the unweighted version, the complexities decrease to O(m 2 log m) time and O(m 2 ) space.

Algorithm 2

 2 . The time to preprocess all O(m) data structures from the corresponding sets T is therefore O(m) • O(m log 2 m). The point p k of maximum weight satisfying k < j and {p i , p j , p k } independent is determined with a single anti-disk maximum query (line 17) on the data structure D j associated with S j . All the O(m 2 ) queries take together O(m 2 )•O(log 2 m) = O(m 2 log 2 m) time. Space is dominated by the O(m) data structures with O(m log m) storage each. To reduce the running time to O(m 2 log m) and the space to O(m 2 ) for the unweighted version, we use the data structure from Lemma 2.4, and the same argument as in the proof of Theorem 3.4 shows that w maxw ret ≤ 3. Maximum (weight) independent set inside a strip of width 1 Input: The set Q of m points p 1 , . . . , p m ordered by x coordinate inside a strip of width 1. Output: A maximum weight independent set of Q. 1: D = array [1 . . . m] of data structure from Lemma 2.3 (weighted) or 2.4 (unweighted) 2: S = array [1 . . . m, 0 . . . m] of integers 3: W = array [1 . . . m, 0 . . . m] of reals (weighted) or integers (unweighted) 4: max = (1, 0) 5: for i = 1, . . . , m do

  and point location[START_REF] Berg | Computational Geometry: Algorithms and Applications[END_REF] Ch. 6]. Alternatively, one can use lifting (called inversion in[START_REF] Berg | Computational Geometry: Algorithms and Applications[END_REF] Ch. 8]), duality[START_REF] Berg | Computational Geometry: Algorithms and Applications[END_REF] Ch. 8], and point location[START_REF] Berg | Computational Geometry: Algorithms and Applications[END_REF] Ch. 6]. Given a set of n planar points, there exists a data structure that answers anti-disk emptiness queries in O(log n) time with O(n) storage and O(n log n) preprocessing time.Lemma 2.3. Given a set of n weighted planar points, there exists a data structure that answers anti-disk maximum queries in O(log 2 n) time with O(n log n) storage and O(n log 2 n) preprocessing time.

	Lemma 2.2. Combining Lemmas 2.1 and 2.2, we have:

6:

S[i, 0] = 0 Represents S i,0 = {p i } 7:

end if

24:

end if

25:

end for 26:

New data structure from set T 27: end for 28: (i, j) = max, IS = {p i } 29: while j = 0 do 30: IS = IS ∪ {p j } 31: i = j, j = S[i, j] 32: end while 33: return IS Combining Lemma 3.1 and Theorem 4.2, we obtain the following theorem. Theorem 4.3. Given a set P of n weighted points, we can compute a 2-approximation to the maximum weight independent set in O(n 2 log 2 n) time and O(n 2 log n) space. In the unweighted version, the complexities decrease to O(n 2 log n) time and O(n 2 ) space.

Polynomial-Time Approximation Scheme

We design a polynomial time approximation scheme (PTAS) for the maximum independent set problem on a given UDG, where the geometric representation of the graph has been given i.e., the center of the unit disks are given. We assume that P be the set of centers of the unit disks associated with the UDG. Also assume that R be an enclosing rectangle of the point set P. To design a PTAS we use two level shifting strategy, proposed by Hauchbaum and Maass [START_REF] Hochbaum | Approximation schemes for covering and packing problems in image process[END_REF]. In the first level of shifting strategy we execute k + 1 iterations as follows: in the i-th iteration (0 ≤ i ≤ k), we partition the region R into disjoint vertical slabs such that (i) the first slab is of width i starting from left, (ii) width of each even slab is 1, and (iii) width of other slab is k (note that width of last slab may be less than k). Therefore, solution of different slabs of width k are non-intersecting.

In an iteration of the first level, we consider only those vertical slabs containing at least one point in P, and compute maximum independent set by applying second level shifting strategy by considering horizontal partition of each vertical slab, add up the solutions of all slabs to get the solution of that iteration. The iteration producing maximum size solution is reported. The proof of the following lemma is presented in [START_REF] Das | Approximation algorithms for maximum independent set of a unit disk graph[END_REF].

Lemma 5.1. If n k is the maximum number of mutually non-overlapping unit disks whose centers lie in a strip of width k > 1 and intersected by a vertical line , then n k ≤ 7k 3 + 2.

Computing MIS for unit disks centered in a k × k square

Let Q ⊆ P be the set of points inside a cell χ of size k×k. Consider a vertical line v and a horizontal line h that partition χ into four sub-cells each of size

of points in the four quadrants whose distance from v and h is greater than 1 2 . To compute a MIS for the set of points in Q, we use the following divide and conquer technique.

Consider all possible subsets Q ⊆ Q( v , h ) of size at most 2 × n k , where n k = 7k 3 + 2 (since 2 × n k is the maximum possible size of the point set in Q( v , h ) that can appear in an optimal solution due to Lemma 5.1). For each of Q , we do the following in each quadrant: delete all the points in Q i (i = 1, 2, 3, 4) which are not independent with Q . Let Q i ⊆ Q i be the remaining set of points. Now compute the optimal solution for Q i recursively using the same procedure. If T (m, k) is the time complexity for finding MIS in χ, then T (m, k) = 4 • T (m, k

2 ) × m 2n k = m O(k) . Thus, we have the following result: Theorem 5.2. Given a set P of n points in the plane and an integer k > 1, the proposed algorithm computes an independent set of size at least 1