Katia Snégaroff

Frédéric Lassagne

Ghenia Bentabed-Ababsa

Ekhlass Nassar

Sidaty Cheikh

Sid Ely

Stéphanie Hesse

Enrico Perspicace

Aïcha Derdour

Florence Mongin
email: florence.mongin@univ-rennes1.fr

Direct metallation of thienopyrimidines using a mixed lithium-cadmium base and antitumor activity of functionalized derivatives

A series of thieno [2,3-d]-and thieno[3,2-d]pyrimidines have been easily synthesized using as key step a deproto-cadmiation-trapping sequence. Some of the compounds thus synthesized were screened for anti-cancer (cytotoxic) activities, and (S)-2-(6-iodo-2-phenylthieno[2,3-d]pyrimidin-4-ylamino)-3-phenylpropanoic acid proved to have a significant activity towards liver, human breast and cervix carcinoma cell lines.

Introduction

Thienopyrimidine derivatives, which are structural analogues of purines, have been drawn attention due to their large range of pharmacological activities. 1 Numerous thieno[2, 3d]pyrimidines have been proved to be phosphodiesterase inhibitors and various receptor antagonists; compounds were designed to act as immunomodulators or to be used in case of cerebral ischemia, malaria, tuberculosis, Alzheimer's and Parkinson's diseases. 1 Many thieno[2, 3-d]-and thieno [3,2d]pyrimidines exhibit antitumor and radioprotective activities. 1 Lithium bases have been largely employed for the deprotometallation of aromatic rings. 2 Nevertheless, for aromatics bearing reactive functions (e.g., ester or cyano groups) or sensitive π-deficient heterocycles, either extremely low reaction temperatures or in situ electrophilic trapping are required due to the high reactivity of the corresponding (hetero)aryllithiums.

The use of metal additives in order to get more efficient or more chemoselective bases is a challenging field, and various R n MLi type compounds already prepared behave as superbases since such species exhibit behaviours that cannot be reproduced by the monometallic compounds on their own. Among them, the R n MLi mixtures of organolithiums and M alkali metal alkoxides described by Schlosser, [START_REF] Schlosser | [END_REF] Lochmann, 4 and Caubère 5 are powerful reagents.

More recently, R n MLi type compounds with M different from an alkali metal have also been described for their 40 unprecedented metallation ability. These species display a large panel of reactivities, depending on both the metal M and the groups connected to it. 6 By combining soft organometallic compounds with lithium additives, bases allowing both efficient and chemoselective reactions have been prepared and 45 used to generate functionalized aromatic compounds. 7 We recently accomplished the deproto-metallation of a large range of aromatics including heterocycles using a newly developed lithium-cadmium base, (TMP) 3 CdLi (TMP = 2,2,6,6-tetramethylpiperidino), 8 and we here describe its use 50 for the functionalization of thieno[2, 3-d]-and thieno [3,2d]pyrimidines. Some intermediates and target compounds were evaluated for their cytotoxic activity.

Results and discussions

Synthetic aspects

55

To this purpose, 4-chlorothieno[2,3-d]pyrimidine (1) was synthesized as described recently under microwave irradiation. 9 4-Chloro-2-phenylthieno [3,2-d] was prepared (as shown in Scheme 1) from commercially available methyl 3-aminothiophene-2-carboxylate by adapting a described procedure. 10 Isomeric 4-chloro-2phenylthieno[2, 3-d]pyrimidine (3) was similarly synthesized, but from known 2-aminothiophene-3-carboxamide. 11 Starting from 4-chlorothieno[2,3-d]pyrimidine (1), a subsequent functionalization at the 4 position was easily achieved either by nucleophilic substitution using sodium methoxide to afford the ether 4, or by copper-catalyzed N-arylation of pyrazole by adapting described conditions 12 to furnish the derivative 5. 4-Chloro-2-phenylthieno[2,3-d]pyrimidine (3) was readily converted by reaction with sodium methoxide or morpholine to the compounds 6 and 7, respectively (Scheme 1).

In contrast to thiophene compounds which can be easily metallated using lithium bases, 13 pyrimidines are much more prone to nucleophilic attacks, 14 and their metallation can only be achieved at room temperature when softer bases are employed. 8,15 The lithium-cadmium base (TMP) 3 CdLi was chosen for the metallation of the thienopyrimidine substrates because of its high compatibility with sensitive heterocycles. 8 20 Conducting the reaction from 4-chloro-(1) and 4methoxythieno[2,3-d]pyrimidine (4) using 0.5 equivalent 8 of base in tetrahydrofuran (THF) at room temperature for 2 h resulted, after quenching with iodine, in the formation of the iodides 8 and 9, respectively (48 and 90% yield). Unlike five-25 membered heterocycles, for which protons adjacent to heteroatoms have the strongest acidity, six-membered heterocycles have the weakest acidic protons adjacent to nitrogens, a result of the more important repulsion between the lone electron pair of nitrogen and the negative charge of 30 the carbanion for the latter, due to the smaller angle between the two electron clouds. 16 As a consequence, the substrates 1 and 4 are regioselectively deprotonated at the most acidic 6 position (Table 1, entries 1,2). Upon treatment with 0.5 equiv of (TMP) 3 CdLi under the same reaction conditions, 4-35 (pyrazol-1-yl)thieno[2, 3-d]pyrimidine (5) did not undergo regioselective deprotonation, and only a mixture of several inseparable derivatives was obtained (Entry 3). Starting from 4-chloro-2-phenylthieno [3,2-d]pyrimidine (2), metallation still took place next to the sulfur atom, as evidenced by 40 trapping with iodine to afford the 6-iodo derivative 10a in 70% yield (compound 10a was identified unequivocally by Xray structure analysis.). † Turning to 1 equivalent of base (instead of 0.5) allowed a slight yield improvement (76%) but also, more importantly, the formation of the diiodide 10b in 45 18% yield. The latter could result from a dideprotonation due to the activation of the site at the 7 position by the close nitrogen atom (Entries 4,5). Isomeric 4-chloro-2phenylthieno[2,3-d]pyrimidine

(3) was similarly functionalized in an excellent yield (Entry 6). By replacing 50 the chloro group with a methoxy or a morpholino group [START_REF] Gros | Note that deprotonation of a morpholino group followed by ring contraction can occur using (trimethylsilyl)methyllithium as base[END_REF] (substrates 6 and 7), the conditions were optimized, and the best yields were obtained using 1 equivalent of base (Entries 7,8).

It also proved possible to trap the metallated 4-(morpholin-55 4-yl)-2-phenylthieno[2, 3-d]pyrimidine prepared from the substrate 7 in a palladium-catalyzed cross-coupling reaction with 2-bromopyridine. Indeed, by using catalytic amounts of palladium acetate and 1,1'-bis(diphenylphosphino)ferrocene (dppf), the expected product 14 was isolated in 70% yield 60 (Scheme 2).

Table 1 Deproto-cadmiation (using (TMP)3CdLi)-iodination. a Metallation took place but not regioselectively, and the products formed could not be separated. In order to progress towards molecules with potential antitumor activities, we decided to prepare thiophene analogues of 2-(6-iodo-2-phenylquinazolin-4-ylamino)-3-phenylpropanoic acid, which proved to exhibit anti-cancer activity (cytotoxic) against U937 leukemia cell lines (Scheme 3). 18 To this purpose, different 2-phenyl-4chlorothienopyrimidines, iodinated or not, were involved in the nucleophilic substitution reaction of the chloride by Lphenylalanine, under the conditions described in the 10 quinazoline series 18 to afford the analogues 15-19 (Table 2, entries 1-5). N-methyl-L-phenylalanine, L-phenylalaninol and L-proline were then used in order to evidence the importance of the secondary amine and carboxylic acid functions (entries 6-8, compounds 20-22).

15

Pharmacology

The compounds 6, 7, 12-14, 16, 19, 20 and21 were tested against a liver carcinoma cell line (HEPG2), a human breast carcinoma cell line (MCF7), and a cervix carcinoma cell line (HELA) (Table 3). The compounds 6, 7, 12, 14 and 16 20 showed a low activity towards the liver carcinoma cell line HEPG2 compared to a reference drug (doxorubicin); the compounds 13, 20 and 21 showed a moderate activity whereas the compound 19 was found to have a very potent activity towards HEPG2 with a IC 50 of 0.40 μg/mL (the IC 50 value for 25 the reference drug, doxorubicin, is 0.70 μg/mL). Concerning the activity towards the human breast carcinoma cell line MCF7, all the compounds showed moderate activities compared to the reference drug doxorubicin except the compound 19 which turned out to be promising. For the 30 cervix carcinoma cell line HELA, all the compounds have low activities compared to the reference drug doxorubicin, except the compounds 6 and 19 which were found to be more effective towards this kind of carcinoma cell line (HELA) than other compounds.

35

Conclusions

A series of thieno[2, 3-d]-and thieno [3,2-d]pyrimidines have been easily synthesized. The key step is a deprotonationtrapping sequence using a mixed lithium-cadmium base. Most Table 3 a In vitro cytotoxic activity (IC50) b of the newly synthesized compounds and doxorubicin against a liver carcinoma cell line (HEPG2), a human breast carcinoma cell line (MCF7), and a cervix carcinoma cell line (HELA). c

Entry Compound HEPG2 (g/mL) MCF7 (g/mL) HELA (g/mL) The cadmium presence in the tested compounds was not evaluated since CdCl2•TMEDA was used at the last but one step, but in case of further development these compounds would have to be synthesized using a safe base and tested again. b IC50 is defined as the concentration which results in a 50% decrease in cell number as compared with that of the control structures in the absence of an inhibitor. c Pharmacological tests have also been performed for compounds 15, 17, 18 and 22, but they failed to give logical results. of the compounds were screened in order to evidence an anticancer activity. Some of them such as (S)-2- (6-iodo-2phenylthieno[2,3-d]pyrimidin-4-ylamino)-3-phenylpropanoic acid (19) showed significant cytotoxic activities towards the tested cell lines, in particular with the liver and human breast 5 carcinoma cell lines.

1

Experimental

Syntheses: general methods Metallation reactions were performed under argon atmosphere. THF was distilled over sodium/benzophenone. Column chromatography separations were achieved on silica gel (40-63 m). Melting points were measured on a Kofler apparatus. 1 H and 13 C Nuclear Magnetic Resonance (NMR) spectra were recorded on a Bruker ARX-200 spectrometer at 200 and 50 MHz, respectively, on a Bruker Avance III spectrometer at 300 and 75 MHz, respectively, or on a Bruker AC-400 spectrometer at 300 and 75 MHz, respectively. 1 H chemical shifts () are given in ppm relative to the solvent residual peak, and 13 C chemical shifts relative to the central peak of the solvent signal. 19 Mass spectra (HRMS) measurements were performed at the CRMPO (Centre 20 Régional de Mesures Physiques de l'Ouest) of Rennes using either a Waters Q-TOF 2 or a Bruker micrOTOF Q II instrument in positive or negative elestrospray CI mode, respectively, or a Micromass MS/MS ZABSpec TOF instrument in EI mode. Elemental analyses were performed at the CRMPO using a Thermo-Finnigan Flash EA 1112 CHNS analyzer. 4-Chlorothieno[2,3-d]pyrimidine (1) 9 and 2-aminothiophene-3-carboxamide 11 were prepared according to described procedures. 2-Benzoylaminothiophene-3-carboxamide and 2phenyl-3H-thieno[2, 3-d]pyrimidin-4-one [START_REF] Sauter | This compound has been described previously[END_REF] were prepared by 30 adapting a described procedure. 10

Methyl 3-benzoylaminothiophene-2-carboxylate was prepared by adapting a described procedure. 10 To a mixture of methyl 3aminothiophene-2-carboxylate (2.2 g, 14 mmol) and Et 3 N (2.4 mL, 17 mmol) in CH 2 Cl 2 (18 mL) at 0°C was added dropwise benzoyl chloride (2.0 mL, 17 mmol). After stirring at room temperature for 3 h, the reaction mixture was diluted with CH 2 Cl 2 and washed with saturated NaHCO 3 and brine. The organic layer was dried over Na 2 SO 4 and concentrated under reduced pressure. The resulting solid was purified by column chromatography on 40 silica gel (eluent: heptane/Et 2 O 96:4 to 80:20) to give methyl 3benzoylaminothiophene-2-carboxylate (3.7 g, 98%) as a white solid: mp 98°C (lit. 21 98-99°C). 22 was prepared by adapting a described procedure. 10 To a solution of methyl 3benzoylaminothiophene-2-carboxylate (2.0 g, 7.6 mmol) in MeOH (80 mL) was added a 25% aqueous NH 3 solution (200 mL). After stirring at 50°C for 17 h, the reaction mixture was concentrated to one-half of its initial volume and the resulting solid was collected to give a mixture of 3-benzoylamino-50 thiophene-2-carboxamide and 2-phenyl-3H-thieno [3,2d]pyrimidin-4-one (0.84 g). To this mixture in MeOH (34 mL) was added a 2 N aqueous NaOH solution (12 mL). After stirring at reflux for 17 h, the reaction mixture was acidified with 1 M HCl until pH 4 and the resulting precipitate was collected to give 55 2-phenyl-3H-thieno [3,2-d]pyrimidin-4-one (0.80 g, 46%) as a white solid: mp > 260°C. HRMS: calcd for C 12 H 8 N 2 OS (M + ) 228.0357, found 228.0348. 22 was prepared by adapting a described procedure. 10 A mixture of 2-phenyl-3H-60 thieno [3,2-d]pyrimidin-4-one (1.6 g, 7.0 mmol) and POCl 3 (16 mL, 0.17 mol) was heated at reflux for 4 h. POCl 3 was then distilled under reduced pressure. The residue was diluted in CH 2 Cl 2 , and neutralized with a cooled saturated NaHCO 3 solution. The aqueous layer was extracted with CH 2 Cl 2 and the 65 combined organic layers were washed with brine, dried over Na 2 SO 4 and concentrated. The resulting solid was purified by column chromatography on silica gel (eluent: heptane/CH 2 Cl 2 100:0 to 0:100) to give 2 (1.5 g, 90%) as a white solid: mp 118-119°C. Anal. Calcd for C 12 H 7 N 2 ClS: C, 58.42; H, 2.86; N, 11.35; 70 S, 13.00. Found: C, 58.08; H, 3.00; N, 11.28; S, 12.98%. 3) was prepared as before but starting from 2-phenyl-3H-thieno[2, 3-d]pyrimidin-4one (1.6 g), and was obtained after recrystallization from AcOEt in a quantitative yield as a white solid: mp 148°C (lit. 23 146°C). 4) 24 To a solution of MeONa in MeOH (0.18 g, 8.0 mmol of Na in 40 mL of MeOH) was added 4-chlorothieno[2,3-d]pyrimidine (1, 0.68 g, 4.0 mmol). After stirring at reflux for 1.5 h, the reaction mixture was quenched with water, extracted with CH 2 Cl 2 , dried over Na 2 SO 4 80 and concentrated. The resulting solid was purified by column chromatography on silica gel (eluent: heptane/AcOEt 70:30) to give 4 (0.45 g, 67%) as a white solid: mp 51°C. Anal. Calcd for C 7 H 6 N 2 OS: C, 50.59; H, 3.64; N, 16.86; S, 19.29. Found: C, 50.89; H, 3.73; N, 16.46; S, 19.21%. 6) was prepared as before from 4-chloro-2-phenylthieno[2,3-d]pyrimidine (3, 0.98 g). Column chromatography on silica gel (eluent: CH 2 Cl 2 /heptane 50:50) afforded 6 (2.1 g, 91%) as a pale yellow solid: mp 90-92°C. Anal. Calcd for C 13 H 10 N 2 OS: C, 64.44; H, 4.16; N, 11.56; 90 S, 13.23. Found: C, 64.53; H, 4.26; N, 11.36; S, 12.74%. 5) was prepared from 4-chlorothieno[2,3-d]pyrimidine (1, 0.68 g) by adapting a described procedure. 25

2-Phenyl-3H-thieno[3,2-d]pyrimidin-4-one

4-Chloro-2-phenylthieno[3,2-d]pyrimidine (2)

4-Chloro-2-phenylthieno[2,3-d]pyrimidine (

4-(Pyrazol-1-yl)thieno[2,3-d]pyrimidine (

4-(Morpholin-4-yl)-2-phenylthieno[2,3-d]pyrimidine (7).

To a solution of morpholine (0.38 g, 4.4 mmol) and 4-chloro-2-100 phenylthieno[2, 3-d]pyrimidine (3, 1.0 g, 4.0 mmol) in dry toluene (25 mL) was added K 2 CO 3 (1.1 g, 8.0 mmol). After stirring at reflux for 1 h, one more equivalent of morpholine was added (0.35 g, 4.0 mmol). The mixture was stirred again for 2 h at reflux, filtered through celite ® , and the filtrate was concentrated 105 under reduced pressure. The resulting solid was purified by column chromatography on silica gel (eluent: CH 2 Cl 2 ) to give 7 (1.0 g, 89%) as a yellow solid: mp 140°C (lit. General procedure for the deproto-cadmiation (using 0.5 equiv (TMP) 3 CdLi)-iodination. To a stirred, cooled (0°C) solution of 2,2,6,6-tetramethylpiperidine (0.25 mL, 1.5 mmol) in THF (5 mL) was added BuLi (about 1.6 M hexanes solution, 1.5 mmol). After 15 min at 0°C, CdCl 2 •TMEDA (0.15 g, 0.5 mmol) was added, and the mixture was stirred for 15 min at this temperature before introduction of the substrate (1.0 mmol). After 2 h at room temperature, a solution of I 2 (0.37 g, 1.5 mmol) in THF (5 mL) was added. The mixture was stirred overnight before addition of an aqueous saturated solution of Na 2 S 2 O 3 (10 mL) and extraction with Et 2 O (3 x 20 mL). The combined organic layers were washed with brine (20 mL), dried over Na 2 SO 4 , filtered, and concentrated under reduced pressure before purification by column chromatography on silica gel (the eluent is given in the product description). 3-d]pyrimidine (1, 0.17 g) following the general procedure. After purification by column chromatography on silica gel (eluent: CH 2 Cl 2 ), compound 8 was obtained as a white solid (0.14 g, 48%): mp 168°C. Anal. Calcd for C 6 H 2 ClIN 2 S: C, 24.30; 20 H, 0.68; N, 9.45; S, 10.81. Found: C, 24.68; H, 1.06; N, 9.12; S, 10.73%. 9) was prepared from 4-methoxythieno[2,3-d]pyrimidine (4, 0.17 g) following the general procedure. After purification by column chromatography on silica gel (eluent: heptane/AcOEt 90:10), compound 9 was obtained as a white solid (0.26 g, 90%): mp 152°C. Anal. Calcd for C 7 H 5 IN 2 OS: C, 28.78; H, 1.73; N, 9.59; S, 10.98. Found: C, 29.09; H, 1.82; N, 9.43; S, 11.43%.

4-Chloro

-6-iodothieno[2,3-d]pyrimidine (8) was prepared from 4-chlorothieno[2,

6-Iodo-4-methoxythieno[2,3-d]pyrimidine (

4-Chloro-6-iodo-2-phenylthieno[3,2-d]pyrimidine (10a) was

prepared from 4-chloro-2-phenylthieno [3,2-d]pyrimidine (2, 0.25 g) following the general procedure. After purification by column chromatography on silica gel (eluent: heptane/CH 2 Cl 2 98:2 to 74:26), compound 10a was obtained as a white solid (0.26 g, 70%): mp 138°C. Anal. Calcd for C 12 H 6 ClIN 2 S: C, 38.68; H, 35 1.62; N, 7.52; S, 8.61. Found: C, 38.69; H, 1.73; N, 7.71; S, 8.32%. 3-d]pyrimidine (3, 0.25 g) following the general procedure. After purification by column 40 chromatography on silica gel (eluent: CH 2 Cl 2 /heptane 50:50), compound 11 was obtained as a white solid (0.36 g, 97%): mp 148°C. Anal. Calcd for C 12 H 6 ClIN 2 S: C, 38.68; H, 1.62; N, 7.52; S, 8.61. Found: C, 39.01; H, 1.92; N, 7.37; S, 8.70%.

4-Chloro

-6-iodo-2-phenylthieno[2,3-d]pyrimidine (11) was prepared from 4-chloro-2-phenylthieno[2,
General procedure for the deproto-cadmiation (using 1 equiv before introduction of the substrate (0.5 mmol). After 2 h at room temperature, a solution of I 2 (0.37 g, 1.5 mmol) in THF (5 mL) was added. The mixture was stirred overnight before addition of an aqueous saturated solution of Na 2 S 2 O 3 (10 mL) and extraction with Et 2 O (3 x 20 mL). The combined organic layers were 55 washed with brine (20 mL), dried over Na 2 SO 4 , filtered, and concentrated under reduced pressure before purification by column chromatography on silica gel (the eluent is given in the product description).

4-Chloro-6,7-diiodo-2-phenylthieno[3,2-d]pyrimidine (10b)

60 was prepared from 4-chloro-2-phenylthieno [3,2-d] 3.33; N, 9.93; S, 7.85. Found: C, 45.11; H, 3.46; N, 9.57; S, 7.36%. 3d]pyrimidine (7, 0.15 g, 0.5 mmol). After 2 h at room temperature, Pd(OAc) 2 (3.4 mg, 15 mol), 1,1'bis(diphenylphosphinoferrocene) (9 mg, 15 mol) and 2bromopyridine (0.48 mL, 0.5 mmol) were added successively, 95 and the mixture was heated at reflux overnight. The mixture was filtered through celite ® , and the cake was washed with CH 2 Cl 2 .

4-(Morpholin

After purification by column chromatography on silica gel (eluent: CH 2 Cl 2 /AcOEt 100:0 to 90:10), and crystallization from acetonitrile, compound 14 was obtained as a yellow solid (0.13 g, General procedure for the nucleophilic substitution of 4chlorothienopyrimidines by an amino acid or derivative. A previously described procedure was adapted. 18 A mixture of the 105 required 4-chlorothienopyrimidine (0.13 mmol) and amino acid or derivative (0.14 mmol), and potassium carbonate (0.59 mmol) in DMSO (0.6 mL) was heated overnight at 100°C. After cooling to room temperature, 1N HCl was added until pH 4. The resulting solid was collected and purified by column chromatography on 22) was prepared from 4chloro-6-iodo-2-phenylthieno[2,3-d]pyrimidine (11, 48 mg) and using L-proline (16 mg) following the general procedure, and was obtained as a pale yellow solid (22 mg, 38%): mp > 240°C.

Pharmacology

The method applied is similar to that reported by Skehan et al. 26 using 20 Sulfo-Rhodamine-B stain (SRB). Cells were plated in 96-multiwell plate (104 cells/well) for 24 h before treatment with 60 the test compound to allow attachment of cell to the wall of the plate. Different concentrations of the compound under test (0, 1.0, 2.5, 5.0, and 10 μg/ml) were added to the cell monolayer in triplicate wells individual dose, and monolayer cells were incubated with the compounds for 48 h at 37 o C and in 65 atmosphere of 5% CO 2 . After 48 h, cells were fixed, washed and stained with SRB stain, excess stain was washed with acetic acid and attached stain was recovered with Tris-EDTA buffer. Color intensity was measured in an ELISA reader, and the relation between surviving fraction and drug concentration is plotted to 70 get the survival curve of each tumor cell line after the specified compound and the IC 50 was calculated. A series of thieno[2, 3-d]-and thieno [3,2-d]pyrimidines have been synthesized using as key step a deproto-cadmiation-trapping sequence. One derivative proved to have a significant activity towards the liver carcinoma cell line HEPG2.

  Scheme 1 Synthesis of the substrates 1-7.

Scheme 3

 3 Scheme 2 Deproto-cadmiation (using (TMP)3CdLi) followed by crosscoupling.

75 4 -

 4 Methoxythieno[2,3-d]pyrimidine (

  To a stirred, cooled (0°C) solution of 2,2,6,6tetramethylpiperidine (0.26 mL, 1.5 mmol) in THF (2 mL) was added BuLi (about 1.6 M hexanes solution, 1.5 mmol). After 15 min at 0°C, CdCl 2 •TMEDA (0.15 g, 0.5 mmol) was added, and the mixture was stirred for 15 min at this temperature before 90 introduction of 4-(morpholin-4-yl)-2-phenylthieno[2,

  mp > 260°C. HRMS: calcd for C 21 H 19 N 4 OS ([M+H] + ) 375.1280, found 375.1282.

  110 silica gel (AcOEt/MeOH 80:20).

16 ) 21 )

 1621 acid (15) was prepared from 4-chloro-2phenylthieno[3,2-d]pyrimidine (2, 32 mg) and using Lphenylalanine(23 mg) following the general procedure, and was obtained as a pale yellow solid (32 mg, 66%): mp > 240°C.HRMS: calcd for C 21 H 16 N 3 O 2 S ([Mwas prepared from 4-chloro-6-iodo-2-phenylthieno[3,2-d]pyrimidine (10a, 48 mg) and using Lphenylalanine (23 mg) following the general procedure, and was obtained as a pale yellow solid (36 mg, 55%): mp > 240°C. HRMS: calcd for C 21 H 15 IN 3 O 2 S ([M[2,3-d]pyrimidine (11, 48 mg) and using Lphenylalanine (23 mg) following the general procedure, and was obtained as a pale yellow solid (52 mg, 80%): mp > 240°C. HRMS: calcd for C 21 H 17 IN 3 O 2 S ([M+H] + ) 502.0086, found 502.0088. (S)-2-[(6-Iodo-2-phenylthieno[2,3-d]pyrimidin-4yl)(methyl)amino]-3-phenylpropanoic acid (20) was prepared from 4-chloro-6-iodo-2-phenylthieno[2,3-d]pyrimidine (11, 48 mg) and using N-methyl-L-phenylalanine (25 mg) following the general procedure, and was obtained as a pale yellow solid (50 40 mg, 74%): mp > 240°C. HRMS: calcd for C 22 H 17 IN 3 O 2 S ([was prepared from4-chloro-6-iodo-2- phenylthieno[2,3-d]pyrimidine(11, 48 mg) and using Lphenylalaninol (21 mg) following the general procedure, and was obtained as a pale yellow solid (25 mg, 40%): mp > 240°C. HRMS: calcd for C 14 H 11 IN 3 OS ([M-C 7 H 7 ] + ) 395.9668, found: 395.9626. (S)-1-(6-Iodo-2-phenylthieno[2,3-d]pyrimidin-4yl)pyrrolidine-2-carboxylic acid (

  HRMS: calcd for C 16 H 14 IN 3 S ([M-CO 2 ] + ) 406.9953, found: 55 406.9925.

Table 2

 2 Nucleophilic substitution of the 4-chlorothienopyrimidines by an amino acid or derivative.

  23 139°C). Anal. Calcd for C 16 H 15 N 3 OS: C, 64.62; H, 5.08; N, 14.13; S, 10.78.

Found: C, 64.79; H, 5.15; N, 14.08; S, 10.43%.

Acknowledgment

3-phenylpropanoic acid

was prepared from 4-chloro-6,7diiodo-2-phenylthieno[3,2-d]pyrimidine (10b, 65 mg) and using L-phenylalanine (23 mg) following the general procedure, and was obtained as a pale yellow solid (39 mg, 48%): mp > 240°C.


Dominique Attali
email: dominique.attali@gipsa-lab.grenoble-inp.fr

André Lieutier
email: andre.lieutier@3ds.com

David Salinas
email: david.salinas@gipsa-lab.grenoble-inp.fr

Vietoris-Rips Complexes also Provide Topologically Correct Reconstructions of Sampled Shapes $

Keywords: Shape reconstruction, Rips complexes, clique complexes, Čech complexes, homotopy equivalence, collapses, high dimensions

Given a point set that samples a shape, we formulate conditions under which the Rips complex of the point set at some scale reflects the homotopy type of the shape. For this, we associate with each compact set X of R n two real-valued functions c X and h X defined on R + which provide two measures of how much the set X fails to be convex at a given scale. First, we show that, when P is a finite point set, an upper bound on c P (t) entails that the Rips complex of P at scale r collapses to the Čech complex of P at scale r for some suitable values of the parameters t and r. Second, we prove that, when P samples a compact set X, an upper bound on h X over some interval guarantees a topologically correct reconstruction of the shape X either with a Čech complex of P or with a Rips complex of P . Regarding the reconstruction with Čech complexes, our work compares well with previous approaches when X is a smooth set and surprisingly enough, even improves constants when X has a positive µ-reach. Most importantly, our work shows that Rips complexes can also be used to provide shape reconstructions having the correct homotopy type. This may be of some computational interest in high dimensions.

Introduction

In this paper, we formulate conditions under which the Rips complex of a point set reflects the homotopy type of the shape that the points sample using measures of how far this shape is from being convex.

Motivation. The problem of reconstructing shapes from point clouds arises in many fields, including computer graphics and machine learning [START_REF] Amenta | The crust and the β-skeleton: Combinatorial curve reconstruction[END_REF][START_REF] Dey | Curve and surface reconstruction: algorithms with mathematical analysis[END_REF]. Maybe one of the simplest reconstruction method is to output an α-offset of the sample points, that is, the union of balls centered at the sample with radius α. Assuming the shape is a smooth manifold [START_REF] Niyogi | Finding the Homology of Submanifolds with High Confidence from Random Samples[END_REF][START_REF] Chazal | Smooth Manifold Reconstruction from Noisy and Non Uniform Approximation with Guarantees[END_REF] or more generally has a positive µ-reach [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF], it has been proved that this method provides indeed an approximation with the correct homotopy type for a sufficiently dense sample and a suitable value of the offset parameter α. Topologically, this is equivalent to computing the α-shape [START_REF] Edelsbrunner | The union of balls and its dual shape[END_REF][START_REF] Edelsbrunner | Three-dimensional alpha shapes[END_REF] of the sample points, which can be obtained by first building the Delaunay triangulation and then keeping simplices that fit in an empty ball of radius α or less.

This approach works well for point clouds in three-dimensional space which have Delaunay triangulations of affordable size [START_REF] Attali | A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces[END_REF][START_REF] Attali | Complexity of the Delaunay triangulation of points on surfaces: the smooth case[END_REF]. But, as the dimension of the ambient space increases, the size of the Delaunay triangulation explodes [START_REF] Amenta | Complexity of Delaunay triangulation for points on lower-dimensional polyhedra[END_REF] and other strategies must be found. If the data points lie on a low-dimensional submanifold, it seems reasonable to ask that the result of the reconstruction depends only upon the intrinsic dimension of the data. This motivated de Silva [START_REF] Silva | A weak characterisation of the Delaunay triangulation[END_REF] to introduce witness complexes and Boissonnat and Ghosh [START_REF] Boissonnat | Manifold reconstruction using tangential Delaunay complexes[END_REF] to define tangential Delaunay complexes. For medium dimensions, Boissonnat and al. [START_REF] Boissonnat | Incremental construction of the Delaunay triangulation and the Delaunay graph in medium dimension[END_REF] have modified the data structure representing the Delaunay complex and are able to manage complexes of reasonable size up to dimension six in practice. In particular, they avoid the explicit representation of all Delaunay simplices by storing only edges in what they call the Delaunay graph, an idea close to that of using Vietoris-Rips complexes developed in this paper.

Vietoris-Rips complexes. Given a point set P and a scale parameter α, the Vietoris-Rips complex is the simplicial complex whose simplices are subsets of points in P with diameter at most 2α. Rips complexes are examples of flag complexes, and as such enjoy the property that a subset of P belongs to the complex if and only if all its edges belong to the complex. In other words, Rips complexes are completely determined by the graph of their edges. This compressed form of storage makes Rips complexes very appealing for computations, at least in high dimensions. Recent results study their simplification through homotopy-preserving edge collapses [START_REF] Zomorodian | Fast construction of the Vietoris-Rips complex[END_REF][START_REF] Zomorodian | The tidy set: a minimal simplicial set for computing homology of clique complexes[END_REF] and edge contractions [START_REF] Attali | Efficient Data Structure for Representing and Simplifying Simplicial Complexes in High Dimension[END_REF]. However, the strategy of using Rips complexes makes sense only if they are able to reflect the topology of the shape that their vertices sample. A closely related family of simplicial complexes are Čech complexes. Specifically, the Čech complex of P at scale α consists of all simplices spanned by points in P that fit in a ball of radius α. The Čech complex of P at scale α is homotopy equivalent to the α-offset of P and therefore also possesses the ability to reproduce the topology of the shape sampled by P . This property was used by Chazal and Oudot [START_REF] Chazal | Towards persistence-based reconstruction in euclidean spaces[END_REF] to extract topological information on the shape from the Rips complex filtration, by interleaving it with the Čech complex filtration and using persistence topology.

The main contribution of this paper is to unveil a more direct relationship between the respective topologies of the Rips complex and the sampled shape. Specifically, we give conditions under which Rips complexes capture the topology of the shape. In a different setting, it has been proved in [START_REF] Hausmann | On the Vietoris-Rips Complexes and a Cohomology Theory for Metric Spaces[END_REF][START_REF] Latschev | Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold[END_REF] that the Rips complex of a point set close enough to a Riemannian manifold for the Gromov-Hausdorff distance shares the homotopy type of the manifold. However, these results focus on smooth manifolds, consider the intrinsic Riemannian metric instead of the Euclidean ambient metric and are not effective since they do not give explicit constants. Nevertheless, they suggest that Rips complexes could be used in practice to produce topologically correct approximations of shapes. If the distances are measured using the ℓ ∞ norm then the Rips complex of P at scale α is equal to the Čech complex of P at scale α and is also homotopy equivalent to the union of hypercubes of side length 2α centered at the points of P [START_REF] Carlsson | Topological approximation by small simplicial complexes[END_REF]. In this case the authors in [START_REF] Attali | Reconstructing shapes with guarantees by unions of convex sets[END_REF] state conditions under which the Rips complex of P reproduces the homotopy type of the shape sampled by P . In this paper we suppose distances are measured using the Euclidean norm. Extensions to more general metric spaces will be evoked in the conclusion.

Partially related to our work, we should mention [START_REF] Chambers | Vietoris-rips complexes of planar point sets[END_REF] which relates the fundamental group of a Rips complex and its shadow (see below) in dimension 2 and give counterexamples in higher dimensions.

Sampling conditions. In any case, it is necessary for a point cloud to be accurate and dense enough to reflect the topology of the shape it samples. The quality of the sample is typically expressed in terms of Hausdorff distance to the shape. Guaranteed reconstruction methods are generally accompanied by results of the following form: if the Hausdorff distance is smaller than some notion of topological feature size of the shape, then the output is topologically correct. First sampling conditions were expressed in terms of the reach, which is the infimum of distances between points in the shape and points in its medial axis [START_REF] Attali | r-regular shape reconstruction from unorganized points[END_REF][START_REF] Amenta | Surface reconstruction by Voronoi filtering[END_REF][START_REF] Boissonnat | Smooth surface reconstruction via natural neighbour interpolation of distance functions[END_REF][START_REF] Niyogi | Finding the Homology of Submanifolds with High Confidence from Random Samples[END_REF][START_REF] Chazal | Smooth Manifold Reconstruction from Noisy and Non Uniform Approximation with Guarantees[END_REF]. Unfortunately, the reach vanishes on sharp concave edges and therefore is not suitable for expressing sampling conditions for non-smooth manifolds or stratified objects. To deal with this problem, authors in [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF] introduce a new characterization of the feature size, the µ-reach, which allows them to formulate sampling conditions for a large class of non-smooth compact subsets of Euclidean space.

In this work, we introduce two new measures of feature size, both called convexity defects. Roughly speaking, they measure how far an object is from being locally convex, in the same manner as curvature measures how far an object is from being locally flat. In Section 5, we use these measures to express sampling conditions first for the Čech complex and second for the Rips complex. Regarding the reconstruction with Čech complexes, our work compares well with previous approaches when X is a smooth set and surprisingly enough, even improve constants when X has a positive µ-reach. Most importantly, this new framework allows us to prove that Rips complexes also provide topologically correct reconstruction, assuming shapes have a positive µ-reach, for µ sufficiently large.

The remaining sections are organized as follows. In Section 2 we present the necessary background and define the Čech complex and the Rips complex. In Section 3 we introduce and study our two convexity defects functions c X : R + → R + and h X : R + → R + that we associate with any non-empty bounded subset X ⊂ R n . Section 4 describes a condition based on c P under which the Rips complex of a point set P at scale α deformation retracts to the Čech complex of P at scale α. This key condition is encapsulated in Theorem 7. In Section 5 we consider a shape X sampled by a point set P and formulate conditions under which either Čech complexes or Rips complexes of P provide approximations of X with the correct homotopy type. We express those conditions first in terms of an upper bound on c X then for shapes with a positive µ-reach. Section 6 concludes the paper.

Background

In this section we introduce the basic definitions and properties needed in the paper and review two well-known examples of simplicial complexes: the Čech complex and the Rips complex.

Metric space, distances, smallest enclosing ball

Throughout this paper, we shall consider subsets of the Euclidean nspace R n for n ≥ 1. The Euclidean distance between two points x and y of R n is denoted xy . Given two subsets X and Y of R n , we write d H (Y | X) = sup y∈Y d(y, X) for the one-sided Hausdorff distance of Y from X, where d(y, X) is the infimum of the Euclidean distances between y and points x in

X. Observe that d H (Y | X) ≤ ε if and only if Y is contained in the ε-offset X ε = {y ∈ R n | d(y, X) ≤ ε}. The Hausdorff distance between X and Y is d H (X, Y ) = max{d H (X | Y ), d H (Y | X)}.
Recall that the diameter of a subset σ of R n is the supremum of distances between pairs of points in σ, which we denote as Diam(σ) = sup p,q∈σ pq . A subset σ is said to be bounded if its diameter is finite.

The closed ball with center z and radius r is denoted B(z, r). Balls will always be assumed to be closed, unless stated otherwise. It is well known that the smallest ball enclosing a non-empty bounded set σ of R n is well-defined (see Appendix A for a proof). We denote its center by Center(σ) and its radius by Rad(σ). Writing Hull(X) for the convex hull of a subset X ⊂ R n and X for the closure of X, it is not hard to check (by contradiction) that Center(σ) ∈ Hull(σ).

The following inequalities will be useful in Section 2.4 for relating Čech and Rips complexes:

1 2 Diam(σ) ≤ Rad(σ) ≤ ϑ n 2 Diam(σ) where ϑ n = 2n n + 1 . (1)
The right most inequality is also known as Jung's Theorem and a short proof can be found in [START_REF] Silva | Coverage in sensor networks via persistent homology[END_REF]. In particular, we have Rad(σ) < 1 √

Abstract simplicial complexes

Let P be a finite set of points in R n . We call any non-empty subset σ ⊂ P an abstract simplex. Its dimension is one less than its cardinality. A i-simplex is an abstract simplex of dimension i. If τ ⊂ σ is a non-empty subset, we call τ a face of σ and σ a coface of τ . An abstract simplicial complex K is a collection of non-empty abstract simplices that contains, with every simplex, the faces of that simplex. The vertex set of the abstract simplicial complex K is the union of its elements, Vert(K) = σ∈K σ. A subcomplex of K is a simplicial complex L ⊂ K. A particular subcomplex is the i-skeleton consisting of all simplices of dimension i or less, which we denote by K (i) . The shadow of K is the subset of R n covered by the convex hull of simplices in K, Shd K = σ∈K Hull(σ), not to be confused with |K|, the underlying space of a geometric realization of K; see [START_REF] Munkres | Elements of algebraic topology[END_REF]. Let N be the cardinality of the vertex set of K. The underlying space |K| of K can be defined (up to a homeomorphism) by considering a map f : Vert(K) → R N -1 that sends the N vertices of K to N affinely independent points in R N -1 and by setting |K| = σ∈K Hull(f (σ)). Generally, |K| and Shd K are not homeomorphic, as illustrated in Figure 1.

We now review two natural ways of constructing an abstract simplicial complex, given as input a finite set of points in R n and a feature scale parameter t ≥ 0. The definitions given below appear in different forms in the literature.

α ϑ 2 α
Figure 1: Left: the Čech complex with parameter α comprises six triangles and is homotopy equivalent to a circle. Middle: the Rips complex with parameter α contains two more triangles and is homeomorphic to a 2-sphere. Its shadow is a topological disk. Right: the Čech complex with parameter ϑ 2 α contains all faces of the 5-simplex and is homeomorphic to a 5-ball.

The Čech complex

The Čech complex C(P, t) is the abstract simplicial complex whose ksimplices correspond to subsets of k + 1 points that can be enclosed in a ball of radius t,

C(P, t) = {σ | ∅ = σ ⊂ P, Rad(σ) ≤ t}.
Equivalently, a k-simplex {p 0 , .

The Rips complex

The Vietoris-Rips complex is a variant of the Čech complex which is easier to compute. The Vietoris-Rips complex, R(P, t) is the abstract simplicial complex whose k-simplices correspond to subsets of k + 1 points in P with diameter at most 2t,

R(P, t) = {σ | ∅ = σ ⊂ P, Diam(σ) ≤ 2t}.
For simplicity, we refer to R(P, t) as the Rips complex. Recall that the flag complex of a graph G, denoted Flag G, is the maximal simplicial complex whose 1-skeleton is G. The Rips complex is an example of a flag complex. More precisely, this is the largest simplicial complex sharing with the Čech complex the same 1-skeleton, R(P, t) = Flag C(P, t) (1) . Generally, R(P, t) and C(P, t) do not share the same topology; see Figure 1. It follows that the Rips complex R(P, t) is generally not homotopy equivalent to the t-offset P t . Our goal in the next section is to find a condition on the point set P which guarantees that |R(P, t)| ≃ |C(P, t)| and therefore |R(P, t)| ≃ P t . Along the way, we will need a result in [START_REF] Silva | Coverage in sensor networks via persistent homology[END_REF] which is a consequence of Equation ( 1) and which says that there is chain of inclusion C(P, t) ⊂ R(P, t) ⊂ C(P, ϑ n t) where ϑ n = 2n n + 1 .

(2)

Convexity defects measures

In this section, we introduce and study two functions that one can associate with any non-empty bounded subset X ⊂ R n and that provide two different ways of measuring convexity defects of X. Based on the first function, we will formulate in Section 4 a condition which suffices to guarantee that the Rips complex of a finite set of points P at scale α deformation retracts to the Čech complex of P at scale α. Based on the second function, we will formulate in Section 5 sampling conditions under which the Čech and Rips complexes of a point set P provide topologically correct reconstructions of a shape X sampled by the points in P .

Definitions and basic properties

To avoid lengthy sentences, we adopt the convention that the subset X ⊂ R n is always assumed to be non-empty and bounded in this section. In particular, any non-empty subset σ ⊂ X is also bounded and thus has a well-defined smallest enclosing ball. We first define the set of centers of X at scale t as the subset (see Figure 2, left):

Centers(X, t) = ∅ =σ⊂X Rad(σ)≤t {Center(σ)}.
Recalling that Hull(X) denotes the convex hull of X, we then extend the notion of convex hull. Specifically, we define the convex hull of X at scale t as the subset (see Figure 2, right)

Hull(X, t) = ∅ =σ⊂X Rad(σ)≤t Hull(σ).
If X is compact then Hull(X, t) is a superset of Centers(X, t). If P is a finite set of points then Hull(P, t) is the shadow of the Čech complex C(P, t).

Definition 1 (Convexity defects functions). Given a subset X ⊂ R n , we associate to X two real-valued functions: the first one c X : R Intuitively, c X and h X can be thought of as functions that measure the convexity defects of X at a given scale. To make this idea precise, observe that if X ⊂ R n is compact, then we have the three equivalences: X convex if and only if c X = 0 if and only if h X = 0. The two convexity functions c X and h X will play a different role. While c P is all we need to study the Rips complex of a finite point set P in Section 4, it turns out that h X is more stable than c X and will be used in Section 5.1 to express sampling conditions in reconstruction theorems. We plotted the graph of the function c P for various finite point sets in Figure 10.

+ → R + is defined by c X (t) = d H (Centers(X, t) | X) and the second one h X : R + → R + is defined by h X (t) = d H (Hull(X, t) | X).
Before studying in more details functions c X and h X in the next two sections, let us make some brief remarks. Because X is a subset of both Centers(X, t) and Hull(X, t), it follows that the two one-sided Hausdorff distances d H (X | Centers(X, t)) and d H (X | Hull(X, t)) vanish. Hence, we could have used in the above definition two-sided Hausdorff distances instead of one-sided Hausdorff distances. The two functions c X and h X both vanish at 0, are increasing in the interval [0, Rad(X)] and become constant above Rad(X). Since Center(σ) ∈ Hull(σ), we have c X ≤ h X . It is easy to check that for a subset X ⊂ R n and two non-negative real numbers t and α, the following three conditions are equivalent: [START_REF] Amenta | Complexity of Delaunay triangulation for points on lower-dimensional polyhedra[END_REF]

h X (t) ≤ α; (2) Hull(X, t) ⊂ X α ; (3) [Rad(σ) ≤ t =⇒ Hull(σ) ⊂ X α ] for all σ ⊂ X.
In particular, we get that h X (t) ≤ t for all t ≥ 0 since Rad(σ) ≤ t =⇒ Hull(σ) ⊂ σ t as a direct consequence of Lemma 1 (below) applied for x = y. Lemma 1. For any non-empty bounded subset σ ⊂ R n , any point x ∈ R n and any point y ∈ Hull(σ), we have that d Proof. Suppose d(x, σ) > xy for otherwise the result is clear. Let B 0 be the smallest ball enclosing σ and let B 1 be the largest ball centered at x whose interior does not intersect σ; see Figure 3. By construction, σ ⊂ B 0 \ B 1 . Recall that the power distance of a point y from a ball B is π B (y) = yz 2r 2 , where z is the center of B and r its radius. Let H 01 be the set of points whose power distance to B 0 is at most as large as the power distance to B 1 . H 01 is a closed half-space which contains the set difference B 0 \ B 1 . In particular, it contains σ and any point y ∈ Hull(σ). Thus, π B 0 (y) ≤ π B 1 (y) and the result follows.

(x, σ) 2 ≤ x -y 2 + Rad(σ) 2 - y -Center(σ) 2 . B 1 H 01 σ B 0 y Center(σ) x Hull(σ)

Characterizing critical values of the distance function

In the previous section we noted that c X (t) ≤ h X (t) ≤ t for all t. The goal of this section is to establish that equality is attained if and only if t is a critical value of the distance function to X. This property will not be used before Section 5 but sheds light on results of Section 4.

We need some definitions. The distance function d(•, X) to the compact set X ⊂ R n maps every point y ∈ R n to its Euclidean distance to X, d(y, X) = min x∈X xy . Although the distance function is not differentiable, it is possible to define a notion of critical points analogue to the classical one for differentiable functions as illustrated in Figure 4. Specifically, Grove defines in [29, page 360] critical points for the distance function to a closed subset of a Riemannian manifold. We recast this definition in our context as follows. Let Γ X (y) = {x ∈ X | d(y, X) = xy } be the set of points in X closest to y: Next lemma provides two characterizations of the critical values of the distance function to a compact set X ⊂ R n , based respectively on the two convexity defects functions c X and h X .

Definition 2. We say that y ∈ R n is a critical point of the distance function d(•, X) if y ∈ Hull(Γ X (y)). The critical values of d(•, X) are the images by d(•, X) of its critical points. y Γ X (y) t X
Lemma 2. For any compact set X ⊂ R n and any real number t > 0, the following three conditions are equivalent: [START_REF] Amenta | Complexity of Delaunay triangulation for points on lower-dimensional polyhedra[END_REF]

t is a critical value of d(•, X); (2) c X (t) = t; (3) h X (t) = t.
Proof. Consider a non-empty bounded subset σ ⊂ R n and a point y ∈ R n . Making x = y in Lemma 1, we observe that if y ∈ Hull(σ) satisfies d(y, σ) ≥ t and Rad(σ) ≤ t, then y = Center(σ) and t = Rad(σ).

Let us prove that (1) =⇒ (2). Consider a critical point y whose distance to X is t and set σ = Γ X (y) as shown in Figure 4. By definition y ∈ Hull(σ) and by construction d(y, σ) = t and Rad(σ) ≤ t. Thanks to our observation, it follows that y = Center(σ) and consequently c X (t) = t. The implication (2) =⇒ (3) follows from c X (t) ≤ h X (t) ≤ t. Let us prove that (3) =⇒ (1). In other words, suppose h X (t) = t and let us prove that t is a critical value of d(•, X). Since X is compact, h X (t) = t means that we can find a compact set ∅ = σ ⊂ X with Rad(σ) ≤ t and y ∈ Hull(σ) such that t = d(y, X) ≤ d(y, σ). Our observation then implies that y = Center(σ), t = Rad(σ) and σ represents a set of points in X with minimum distance to y. Since y ∈ Hull(σ) ⊂ Hull(Γ X (y)), it follows that y is a critical point of the distance function to X, which concludes the proof.

An adaptation of Morse theory to distance functions tells us that changes in the topology of t-offsets X t occur when the offset parameter t reaches critical values of the distance function to X. Indeed, slightly recasting Proposition 1.8 in [29, page 362], we have: Theorem 3 (Isotopy Theorem [START_REF] Grove | Critical point theory for distance functions[END_REF]). Let X ⊂ R n be a compact set and let β ≥ α > 0 be two real numbers. If the distance function d(•, X) has no critical values in the interval [α, β], then X β deformation retracts to X α .

Our characterizations of critical values allow us to reexpress the condition in the above theorem. To be specific, we get that if c X (t) < t for all t ∈ [α, β], then X β deformation retracts to X α . Replacing X by a finite point set P and using that the Čech complex C(P, t) is homotopy equivalent to the t-offset P t , we obtain that C(P, β) is homotopy equivalent to C(P, α) whenever c P (t) < t for all t ∈ [α, β]. We shall see in Section 4 that under the same condition a stronger result holds, namely the existence of a sequence of collapses from C(P, β) to C(P, α). Strengthening this condition, we will be able to guarantee the existence of a sequence of collapses from R(P, β) to C(P, α). Variants of this condition will then be devised in Section 5 to ensure topologically correct reconstruction of shapes by Čech or Rips complexes.

Stability

In this section, we state the stability of c X and h X . For technical reasons, we need the stability of c P under perturbations of P at the end of the proof of Theorem 7 in Section 4 to relax the assumption that the finite point set P that we consider is in general position. The stability of h X under perturbation of X will be crucial for establishing reconstruction theorems in Section 5. Lemma 4. For every pair of subsets X and Y of R n such that d H (X, Y ) ≤ ε and for every t ≥ 0, we have

c Y (t) ≤ c X (t + ε) + √ 2tε + ε 2 + ε.
Proof. Consider a non-empty subset σ ⊂ Y with Rad(σ) ≤ t and set ξ = X ∩ σ ε . By construction, ξ is non-empty and d H (ξ, σ) ≤ ε. Hence, setting δ = √ 2tε + ε 2 , Lemma 16 implies that Rad(ξ) ≤ t + ε and Center(σ) -Center(ξ) ≤ δ. We get

Center(σ) ⊂ Center(ξ) δ ⊂ X c X (t+ε)+δ ⊂ Y c X (t+ε)+δ+ε ,
yielding to the result. Lemma 5. For every pair of subsets X and P of R n such that d H (X, P ) ≤ ε and for every t ≥ 0, we have h

P (t) ≤ h X (t + ε) + 2ε.
Proof. Consider a non-empty subset σ ⊂ P with Rad(σ) ≤ t and set ξ = X ∩ σ ε . By construction, ξ is non-empty and d H (ξ, σ) ≤ ε. Hence, Lemma 16 implies that Rad(ξ) ≤ t + ε. Using Hull(ξ ε ) = Hull(ξ) ε , we get that Hull(σ) ⊂ Hull(ξ) ε ⊂ X h X (t+ε)+ε ⊂ P h X (t+ε)+2ε , yielding the result.

From Rips to Čech complexes

In this section, we introduce a 2-parameter family of Rips complexes and give the precise condition on a finite point set for which we can prove that a Rips complex in this family deformation retracts to a Čech complex. We begin by defining this family of Rips complexes and state our results in Section 4.1. We then introduce the tools we need to prove our results in Section 4.2. The proofs are presented in Section 4.3.

Quasi Rips complexes and statement of results

Following [START_REF] Chambers | Vietoris-rips complexes of planar point sets[END_REF], we first define a 2-parameter family that contains prior Rips complexes as a subfamily. The motivation for this construction is to account for the uncertainty of measures by allowing uncertainty of the edges belonging to Rips complexes in the family; see [START_REF] Chambers | Vietoris-rips complexes of planar point sets[END_REF]. Definition 3. For any point set P ⊂ R n and any real numbers α, β ≥ 0 with α ≤ β, we call the flag complex of any graph G satisfying R(P, α) ⊂ Flag G ⊂ R(P, β) an (α, β)-quasi Rips complex of P .

In other words, the simplicial complex Flag G is an (α, β)-quasi Rips complex of P if and only if every pairs of points in P within distance 2α are connected by an edge in G and no edge of G has length larger than 2β.

Equivalently, for every pairs (p, q) ∈ P 2 , pq ≤ 2α implies pq ∈ G and p-q > 2β implies pq ∈ G. In particular, K is an (α, α)-quasi Rips complex of P if and only if K = R(P, α).

To state our results, it is convenient to define α to be an inert value of P if Rad(σ) = α for all non-empty subsets σ ⊂ P . The finiteness of P implies that P has only finitely many non-inert values. Thus, assuming α to be inert is not a too restrictive hypothesis.

As a warm-up, we first state conditions in Theorem 6 (below) under which there exists a sequence of elementary collapses which transform one Čech complex into another one. We recall that an elementary collapse is the operation that removes a pair of simplices (σ, τ ) from a simplicial complex K assuming τ is the unique proper coface of σ in K. The result is a simplicial complex K \ {σ, τ } to which K deformation retracts. Theorem 6. Let P ⊂ R n be a finite set of points. For any real numbers β ≥ α ≥ 0 such that α is an inert value of P and c P (t) < t for all t ∈ [α, β], there exists a sequence of elementary collapses from C(P, β) to C(P, α).

Theorem 6 can be thought of as a combinatorial version of the Isotopy theorem presented in Section 3.2. We are now ready to state our main theorem:

Theorem 7. Let P ⊂ R n be a finite set of points. For any real numbers β ≥ α ≥ 0 such that α is an inert value of P and c P (ϑ n β) < 2αϑ n β, there exists a sequence of elementary collapses from any (α, β)-quasi Rips complex of P to the Čech complex C(P, α).

Note that choosing β = α in the theorem gives conditions under which |R(P, α)| ≃ |C(P, α)| ≃ P α . Figure 7 on the left provides a graphical representation of the hypothesis of the theorem. Let us sketch quickly the proof of Theorem 7. Observe that the condition c P (ϑ n β) < 2αϑ n β implies that c P (t) < t for all t ∈ [α, ϑ n β] since

c P (t) ≤ c P (ϑ n β) < 2α -ϑ n β ≤ α ≤ t, whenever α ≤ t ≤ ϑ n β.
Theorem 6 then implies that there exists a sequence of collapses reducing C(P, ϑ n β) to C(P, α). Since any (α, β)-quasi Rips complex Flag G is nested between C(P, α) and C(P, ϑ n β), the key idea in the proof of the above theorem is to monitor changes in the complex C(P, t) ∩ Flag G as we decrease the scale parameter t from ϑ n β to α, that is as we go from C(P, ϑ n β) to Flag G. The proof is given in Section 4.3. Before embarking in the proof, we will define collapses and extended collapses in the next section.

Extended collapses

In this section, we introduce collapses and extended collapses which will turn out to be convenient to describe changes that occur in the families of complexes that we consider in our proof of Theorem 7.

We need some definitions. The inclusion defines a partial order relation on simplices. Given a set of simplices Σ and a simplex σ ∈ Σ, we say that σ is inclusion-maximal in Σ if σ has no proper coface in Σ. Similarly, we say that σ is inclusion-minimal if it has no proper face in Σ. When clear from the context we will omit Σ. Suppose σ is a simplex of the simplicial complex K. The star of σ in K, denoted St K (σ), is the collection of simplices of K having σ as a face. The closure of St K (σ) is denoted St K (σ); it is the smallest simplicial complex containing St K (σ). The link of σ in K, denoted Lk K (σ), is the collection of simplices of K lying in St K (σ) that are disjoint from σ. A simplicial complex K is said to be a cone if it contains a vertex o such that the following implication holds: σ ∈ K =⇒ σ ∪ {o} ∈ K. The vertex o is called the apex of the cone. By definition a cone can never be empty since it always contains at least its apex. Given a simplicial complex K, we are interested in the operation that removes the entire star of a simplex σ ∈ K as illustrated in Figure 8. Provided that there is a unique inclusion-maximal simplex τ = σ in the star of σ, it is well-known that |K| deformation retracts to |K \ St K (σ)| and the operation that removes St K (σ) is then called a collapse [START_REF] Edelsbrunner | Computational topology: an introduction[END_REF]. Any collapse can be decomposed into a finite sequence of elementary collapses. Following and extending what was done in [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF], we call the operation that removes St K (σ) assuming the weaker condition that the link of σ is a cone an extended collapse. Our terminology finds its justification in the following lemma. Lemma 8. Let K be a simplicial complex and let σ be a simplex of K. If the link of σ is a cone, then there is a sequence of collapses from K to K \St K (σ).

Proof. First, we establish that a cone L can always be reduced to its apex o by a sequence of collapses. Suppose L = {o} for otherwise the result is clear and consider an inclusion-maximal simplex in L. It has the form α ∪ {o} with o ∈ α ∈ L. Let us prove that the operation that removes the pair of simplices (α, α ∪ {o}) is a collapse. If β is a coface of α, then β ∪ {o} is a coface of α ∪ {o}. Since α ∪ {o} is inclusion-maximal, the only possibility is that β ∪ {o} = α ∪ {o}, showing that all cofaces of α are faces of α ∪ {o}. Thus, removing the pair (α, α ∪ {o}) is a collapse and the result is still a cone with apex o but with a smaller number of simplices. By repeating the process we eventually get a complex reduced to {o}. Now, suppose the link of σ in K is a cone L with apex o. We deduce from the previous sequence of collapses that reduces L to {o} a sequence of collapses that reduces K to K \ St K (σ) as follows. To each collapse that removes the pair (α, α ∪ {o}) in L described above, we associate the collapse that removes the pair (σ ∪ α, σ ∪ α ∪ {o}) in K. Indeed, since α has a unique proper coface α ∪ {o} in L, it follows that σ ∪ α has a unique proper coface σ ∪ α ∪ {o} in K. At the end of this sequence of collapses, the link of σ is reduced to {o}. After a last collapse that removes the pair (σ, σ ∪ {o}) we get K \ St K (σ).

Proof of results

We will prove directly Theorem 7 and omit the proof of Theorem 6 since one can easily derive a proof of Theorem 6 by slightly adapting the first part of the proof below.

Proof of Theorem 7. Let G be a graph whose flag complex is an (α, β)-quasi Rips complex of P . For t ≥ 0, consider the simplicial complex F(t) = C(P, t) ∩ Flag G. Clearly, we have the chain of inclusions:

C(P, α) ⊂ R(P, α) ⊂ Flag G ⊂ R(P, β) ⊂ C(P, ϑ n β)
and therefore F(α) = C(P, α) and F(ϑ n β) = Flag G. As we continuously increase the feature parameter t from α to ϑ n β, we get a finite family of nested Čech complexes:

C(P, α) = C 0 ⊂ C 1 ⊂ • • • ⊂ C k = C(P, ϑ n β).
For 0 < i < k, let t i be the smallest value of t such that C i = C(P, t) and set F i = F(t i ). In particular, C i = C(P, t i ) and

F i = C i ∩ Flag G.
Correspondingly, we get a 1-parameter family of simplicial complexes by intersecting each complex C i in the above sequence with Flag G:

C(P, α) = F 0 ⊂ F 1 ⊂ • • • ⊂ F k = Flag G.
Let us first assume that P satisfies the two generic conditions (⋆) and (⋆⋆) instead of the condition that Rad(σ) = α for all non-empty subsets σ ⊂ P :

(⋆) For all simplices σ, τ ⊂ P , if Rad(σ) = Rad(τ ) then Center(σ) = Center(τ ); (⋆⋆) For any ball B, the set of simplices in P that have B as a smallest enclosing ball is either empty or has a unique inclusion-minimal element.

Under these two conditions, we prove the theorem in two stages. First, we show that C i-1 is a collapse of C i for all 0 < i ≤ k. Secondly, we show that F i-1 is either equal or an extended collapse of F i for all 0 < i ≤ k.

(a) Because of condition (⋆), all simplices in the set difference C i \ C i-1 share the same smallest enclosing ball B(z i , t i ) with center z i and radius t i . Because of condition (⋆⋆), the set of simplices sharing the same smallest enclosing ball B(z i , t i ) has a unique inclusion-minimal element σ i . Our plan is to prove that C i \ C i-1 is the star of σ i and has a unique inclusion-maximal element τ i = σ i which will entail that C i collapses to C i-1 . Suppose η is a coface of σ i in C i . Since σ i ⊂ η, we deduce that t i = Rad(σ i ) ≤ Rad(η) and therefore η ∈ C i \ C i-1 . Hence, C i \ C i-1 is the star of σ i in C i . Note that the simplex τ i = {p ∈ P | z ip ≤ t i } obtained by gathering all points of P in B(z i , t i ) belongs to C i \ C i-1 and is the unique inclusion-maximal simplex in this set difference (see Figure 6, left). To prove that C i collapses to C i-1 , it remains to establish that σ i = τ i . By choice of σ i as an inclusion-minimal element amongst simplices with smallest enclosing ball B(z i , t i ), the vertices of σ i all lie on the sphere with center z i and radius t i . On the other hand, by definition of c P (t i ) as the one-sided Hausdorff distance of the centers of P at scale t i from P , there exists at least a point o of P at distance c P (t i ) or less from the center z i . Since c P (t i ) ≤ c P (ϑ n β) < α ≤ t i , the point o belongs to the interior of B(z i , t i ). Thus, o ∈ σ i , o ∈ τ i , and therefore

σ i = τ i , showing that C i collapses to C i-1 .
(b) Let us now turn our attention to F i and

F i-1 . If σ i ∈ F i , then F i = F i-1 . If σ i ∈ F i , the star of σ i in F i is equal to the star of σ i in C i t i z i o p Flag G σ i τ i C i \ C i-1 F i \ F i-1 c P (t i )
Figure 6: Notation for the proof of Theorem 7. Left: τ i is the simplex whose vertices are points of P in B(z i , t i ). σ i is the face obtained by keeping vertices on the boundary of B(z i , t i ). Right: Schematic representation of simplices in

C i \ C i-1 .
intersection the flag of G and 6, right). Let us prove that the link of σ i in F i is a cone with apex o, which guarantees that F i-1 is an extended collapse of F i . Suppose η is a coface of σ i in F i and let us show that η ∪ {o} is also a coface. Clearly, η ∪ {o} belongs to the Čech complex C i since for all points p ∈ η ∪ {o}, z ip ≤ t i . Let us prove that η ∪ {o} also belongs to Flag G. Since η belongs to Flag G, it suffices to prove that all edges connecting o to a vertex p of η have length 2α or less. Indeed, for all points p ∈ η, we have

F i-1 = F i \ St F i (σ i ) (see Figure
p -o ≤ z i -p + z i -o ≤ t i + c P (t i ) ≤ 2α
showing that η ∪ {o} ∈ Flag G. Hence, η ∪ {o} belongs to F i . Setting η = σ i , we get that σ i ∪ {o} is a coface of σ i and since o ∈ σ i , it follows that {o} belongs to the link of σ i in F i . Hence, the link of σ i in F i is a cone, which concludes the proof of Theorem 7 assuming generic conditions (⋆) and (⋆⋆) instead of the condition Rad(σ) = α for all non-empty subsets σ ⊂ P .

If P does not satisfy the generic conditions (⋆) and (⋆⋆), we use Lemma 17 in Appendix B to find a perturbation f of the points such that f (P ) satisfies (⋆) and (⋆⋆) and conditions (i), (ii) and (iii) of Lemma 17 for some β ′ > β. Applying Theorem 7 to f (P ) with the values α and β ′ , we get that there exists a sequence of collapses from the (α, β ′ )-quasi Rips complex Flag f (G) = f (Flag(G)) to the Čech complex C(f (P ), α) = f (C(P, α)). Hence, the theorem also holds in the non-generic case.

Shape reconstruction

In this section, we are interested in reconstructing a compact set X ⊂ R n only known through a finite set of possibly noisy points P ⊂ R n . Using the convexity defect function h X , we formulate two sampling conditions which guarantee respectively that the Čech complex and the Rips complex of P are homotopy equivalent to any arbitrarily small offset of X (Section 5.1). We then construct a bridge between shapes with an upper bounded convexity defects function and shapes with a lower bounded critical function in Section 5.2. Finally, we compute in Section 5.3 the lowest density of points authorized by our theorems for a correct reconstruction of shapes with a positive µ-reach.

Sampling conditions based on convexity defects functions

We assemble the pieces and deduce conditions under which the Čech complex and the Rips complex of a finite set of points retrieve the topology of the shape the points sample. Throughout the section, X designates a compact subset of R n and P is a finite set of points, whose Hausdorff distance to X is ε or less.

Reconstruction with the Čech complex. The assumption that d H (X, P ) ≤ ε implies the following chain of inclusions:

P α ⊂ X α+ε ⊂ P α+2ε ⊂ X α+3ε .
From [START_REF] Attali | Reconstructing shapes with guarantees by unions of convex sets[END_REF], we know that whenever we consider four nested spaces P 0 ⊂ X 0 ⊂ P 1 ⊂ X 1 such that X 1 deformation retracts to X 0 and P 1 deformation retracts to P 0 , then X 0 deformation retracts to P 0 . Applying this result to our context combined with the Isotopy Theorem and the characterization of critical points given in Lemma 2, we deduce immediately that X α+ε deformation retracts to P α whenever the following two conditions are fulfilled:

h X (t) < t, ∀t ∈ [α + ε, α + 3ε], h P (t) < t, ∀t ∈ [α, α + 2ε].
Since d H (X, P ) ≤ ε, Lemma 5 implies that h P (t) ≤ h X (t + ε) + 2ε and therefore the above two conditions are fulfilled as soon as the following stronger condition holds:

h X (t) < t -3ε, ∀t ∈ [α + ε, α + 3ε]. Because h X is non- negative, this condition implies that 2ε < α. Because h X is increasing, it also implies that h X (t) < t for all t ∈ [α -2ε, α + 3ε],
showing that η-offsets of X for η in the interval [α -2ε, α + 3ε] are all homotopy equivalent. We summarize our findings in the following theorem:

Theorem 9. Let ε, α > 0 such that 2ε < α. Let P be a finite set of points whose Hausdorff distance to a compact subset X is ε or less. The Čech complex C(P, α) is homotopy equivalent to

X η for all η ∈ [α -2ε, α + 3ε] whenever h X (t) < t -3ε for all t ∈ [α + ε, α + 3ε]. t α + ε ϑ n α 2ε ε Z 9 Z 7 Z 10 t -3ε 2 ϑn -1 t 2 ϑn -1 (t -ε) -2ε t R t t µ = 1 R µ = 1 2 µ = 1 3 µ = 0
Figure 7: Left: For i ∈ {7, 9, 10}, the hypotheses of Theorem i are depicted as regions Z i avoided by the graph of a convexity defects function. Specifically, if c P ∩ Z 7 = ∅, Theorem 7 implies R(P, α) ≃ P α . If h X ∩ Z 9 = ∅, Theorem 9 implies C(P, α) ≃ X α-2ε . If h X ∩ Z 10 = ∅, Theorem 10 implies R(P, α) ≃ X 2α-ϑnα-2ε . Right: Upper bound on h X for µ ∈ {0, 1 3 , 1 2 , 1} provided by Lemma 12.

Reconstruction with the Rips complex. If furthermore we suppose that the condition c P (ϑ n β) < 2αϑ n β holds, we can apply Theorem 7 and deduce that (α, β)-quasi Rips complexes of P deformation retracts to the Čech complex C(P, α). Using Lemma 5, we get that c P (ϑ n β) ≤ h P (ϑ n β) ≤ h X (ϑ n β + ε) + 2ε and the hypothesis of Theorem 7 is fulfilled whenever

h X (ϑ n β + ε) < 2α -ϑ n β -2ε. Because h X is non-negative, this condition implies that 2ε < 2α -ϑ n β. Because h X is increasing, it also implies that h X (t) < t -3ε, ∀t ∈ [α + ε, α + 3ε
] and the hypothesis of Theorem 9 is also fulfilled. We deduce the following theorem:

Theorem 10. Let ε, α and β be three non-negative real numbers such that α ≤ β and 2ε < 2αϑ n β. Let P be a finite set of points whose Hausdorff distance to a compact subset X is ε or less. Then, any (α, β)-quasi Rips complex of P is homotopy equivalent to X η for all η ∈ [2α-ϑ n β -2ε, ϑ n β +ε] whenever α is an inert value of P and h X (ϑ n β + ε) < 2αϑ n β -2ε.

Connections with the critical function

In this section, we show that the class of shapes with an upper bounded convexity defect function are equivalent to the class of shapes with a lower bounded critical function. To make this idea precise, we need to recall the definition of critical functions instrumental in expressing sampling conditions for a class of shapes larger than those with a positive reach in [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF]. Even though the distance function to X is not differentiable, it is possible to define a generalized gradient function ∇ X : R n \ X → R n that coincides with the usual gradient at points where d(•, X) is differentiable and that vanishes precisely at points that are critical [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF]. Specifically, y,X) .

∇ X (y) = y -Center(Γ X (y)) d(

The critical function χ

X : R * + → R + is defined by χ X (t) = inf d(y,X)=t ∇ X (y) .
Clearly, the critical function vanishes at t if and only if t is a critical value of the distance function. Thus, by Lemma 2, we have the equivalences:

χ X (t) = 0 ⇐⇒ c X (t) = t ⇐⇒ h X (t) = t.
The next two lemmas strengthen this fact. Our first lemma provides a lower bound on χ X at t, assuming an upper bound on c X at t.

Lemma 11. For all compact set X ⊂ R n , all 0 ≤ µ ≤ 1 and all t ≥ 0, the following implication holds:

c X (t) < (1 -µ)t =⇒ χ X (t) > µ.
Proof. Consider y ∈ R n such that d(y, X) = t and let us prove that ∇ X (y) > µ. Let σ = Γ X (y) be the set of points in X with minimum distance to y; see Figure 8, left. Suppose the smallest ball enclosing σ has center z and radius s. Since s ≤ t, we get c X (s) ≤ c X (t) < (1µ)t and thus t -

y -z ≤ d(z, X) ≤ c X (s) < (1 -µ)t. It follows that ∇ X (y) = z-y t > µ.
Next lemma can be thought of as a converse of the previous lemma, since it provides an upper bound on h X over the interval [0, R], assuming a lower bound on the critical function χ X over the interval (0, R). It extends a result in [START_REF] Attali | Reconstructing shapes with guarantees by unions of convex sets[END_REF] which says intuitively that the convex hull of point set σ ⊂ X cannot be too far away from a shape X, assuming σ can be enclosed in a ball of small radius t and X has a positive reach. Lemma 12. Consider two real numbers µ ∈ (0, 1] and R ≥ 0. Let X ⊂ R n be a compact set such that χ X (t) ≥ µ for all t ∈ (0, R). Then, for all 0 ≤ t ≤ R, one has:

h X (t) ≤ 1 + µ(1 -µ) -1 -µ(2 -µ) t R 2 µ(2 -µ) R.
Proof. Given σ ⊂ X with Rad(σ) ≤ R and y 0 ∈ Hull(σ), we establish an upper bound on d(y 0 , X) expressed as a function of Rad(σ). The first step in the proof is to find a point y T that is "sufficiently" far away from X by following an integral line of the generalized gradient ∇ X that originates at y 0 . Let X c = R n \ X. The author in [START_REF] Lieutier | Any open bounded subset of R n has the same homotopy type as its medial axis[END_REF] established that there exists a continuous map Φ X : R + × X c → X c such that:

d dt + Φ X (t, y) = ∇ X (Φ X (t, y))
where d dt + denotes the right derivative. Hence, Φ X is a flow and the integral line t → Φ X (t, y 0 ) is a rectifiable curve starting at y 0 . This curve either has infinite length or ends up at a critical point of the distance function to X. If for some T > 0 the set Φ X ([0, T ], y 0 ) contains no critical point then it can be parameterized by a continuous function C y 0 : [0, L] → R n such that C y 0 (0) = y 0 and the length of C y 0 ([0, s]) is s; see Figure 8, right. Let us prove that under the assumption of the lemma we can choose T = Rd(y 0 , X). For all s < Rd(y 0 , X), we note that d(y s , X) ≤ d(y 0 , X) + y sy 0 ≤ d(y 0 , X) + s < R and therefore χ X (d(y s , X)) ≥ µ which implies ∇ X (y s ) ≥ µ. It follows that the integral line C y 0 does not reach any critical point as long as s < R-d(y 0 , X) and C y 0 can at least be parameterized on the interval [0, R-d(y 0 , X)]. Hence, we can set T = R-d(y 0 , X). It has been established in [START_REF] Lieutier | Any open bounded subset of R n has the same homotopy type as its medial axis[END_REF][START_REF] Chazal | The λ-medial axis[END_REF] that:

∀s ∈ [0, L) , d ds + d (C y 0 (s), X) = ∇ X (C y 0 (s)) Integrating over the interval [0, T ], we get d(y T , X) -d(y 0 , X) T ≥ µ.
Applying Lemma 1 with x = y T and y = y 0 gives d(y T , σ) 2 ≤ T 2 + Rad(σ) 2 from which we deduce that

(d(y 0 , X) + µT ) 2 ≤ d(y T , X) 2 ≤ d(y T , σ) 2 ≤ T 2 + Rad(σ) 2 . Plugging T = R -d(y 0 , X), setting δ = d(y 0 ,X) R , ρ = Rad(σ)

R

and rearranging this inequality gives us

µ(2 -µ)δ 2 -2(1 + µ -µ 2 )δ + 1 -µ 2 + ρ 2 ≥ 0. Since δ ≤ 1 we get δ ≤ 1+µ(1-µ)- √ 1-ρ 2 µ(2-µ) µ(2-µ)
, yielding the result.

The upper bound on h X is an arc of ellipse which tends to an arc of parabola as µ → 0; see Figure 7, right. Note that since h X (t) ≤ t for all t, this upper bound is only relevant when under the diagonal. For µ = 1, we get h X (t) ≤ R -√ R 2t 2 as in [START_REF] Attali | Reconstructing shapes with guarantees by unions of convex sets[END_REF]. Equivalently, the graph of h X is below the circle with radius R and center (0, R).

Reconstructing shapes with a positive µ-reach

Shapes with a positive µ-reach form a large class of objects, that unlike shapes with a positive reach, may possess sharp concave edges. Precisely, for 0 < µ ≤ 1, authors in [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF] define the µ-reach of X as r µ (X) = inf {t > 0 | χ X (t) < µ}. The terminology comes from the fact that r 1 (X) coincides with the usual reach of X.

Given a shape X whose µ-reach is greater than or equal to R > 0 and a finite point set P such that d H (P, X) ≤ ε, we compute the largest value of the ratio ε R for which the Čech complex C(P, α) or the Rips complex R(P, α) provide a topologically correct reconstruction of X for a suitable value of the parameter α. Computations were realized using a computer algebra system and details are skipped. In Appendix C, we give all the details when µ = 1, R = 1 and n = +∞.

n ε rips n (1) R n µ * n (a) (b) (c) µ 2 5µ 2 +12 λ cech (µ) λ rips 2 (µ) λ rips +∞ (µ) µ * 2 µ * ∞ µ Figure 9: (a)
Best ratios ε R we can get for a correct reconstruction of a shape with a positive µ-reach either with the Čech or Rips complex for n ∈ {2, 3, 4, 5, +∞}; comparison with the ratio µ 2 5µ 2 +12 obtained in [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF]. (b) and (c) µ * n and λ rips n (1) as functions of n.

Reconstruction with the Čech complex. Note that our assumption r µ (X) ≥ R is equivalent to χ X (t) ≥ µ for all t ∈ (0, R). It follows that a shape X with r µ (X) ≥ R satisfies the hypothesis of Lemma 12 and therefore has a convexity defects function h X upper bounded by a function that depends upon R and µ.

Plugging this upper bound in Theorem 9, we obtain that if α + 3ε ≤ R then the Čech complex C(P, α) is homotopy equivalent to X η for all 0 < η < R whenever the following inequality holds for all t ∈ [α + ε, α + 3ε]:

1 + µ(1 -µ) -1 -µ(2 -µ) t R 2 µ(2 -µ) R < t -3ε.
Eliminating the square root, we can replace the above inequality by H µ,ε (t) < 0 where H µ,ε (t) is a polynomial of degree 2 in t. It follows that the above condition holds whenever the absolute difference between the two roots t

1 µ (ε) ≤ t 2 µ (ε) of H µ,ε (
t) is greater than 2ε. When this happens, the admissible values of α range in the interval

I µ (ε) = [t 1 µ (ε) -ε, t 2 µ (ε) -3ε]. The condition t 2 µ (ε) -t 1
µ (ε) > 2ε can be rewritten as the positivity of a polynomial of degree 2 in ε with two roots, one positive and one negative. Thus, the condition holds whenever ε is smaller than the positive root whose value divided by R is:

λ cech (µ) = -3µ + 3µ 2 -3 + -8µ 2 + 4µ 3 + 18µ + 2µ 4 + 9 + µ 6 -4µ 5 -7µ 2 + 22µ + µ 4 -4µ 3 + 1 .
We thus get the following reconstruction theorem:

Theorem 13. Consider a finite set of points P and a compact subset X whose µ-reach R is positive. If

d H (P, X) ≤ ε < λ cech (µ) R
then C(P, α) is homotopy equivalent to X η for all η ∈ (0, R) and all α ∈ I µ (ε).

Interestingly, λ cech (µ) does not depend on the ambient dimension n. Plotting λ cech (µ) as a function of µ (see Figure 9(a)), we observe that it is positive for all µ ∈ (0, 1] and improves on the upper bound µ 2 5µ 2 +12 established in [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF]. Still, for µ = 1, we get λ cech (1) = -3+ √ 22 13 ≈ 0.13 which is not as good as the value 3 -√ 8 ≈ 0.17 obtained in [START_REF] Niyogi | Finding the Homology of Submanifolds with High Confidence from Random Samples[END_REF].

Reconstruction with the Rips complex. Combining Theorem 10 with β = α and Lemma 12, we get that if ϑ n α + ε ≤ R then the Rips complex R(P, α) is homotopy equivalent to X η for all 0 < η < R whenever

1 + µ(1 -µ) -1 -µ(2 -µ) ϑnα+ε R 2 µ(2 -µ) R < 2α -ϑ n α -2ε.
As before, we can eliminate the square root, replacing the above inequality by H µ (ε, α) < 0 where H µ (ε, α) is a polynomial of degre 2 in ε and α. Since we are looking for the greatest value of ε for which H µ (ε, α) < 0, we may assume that ∂Hµ(ε,α) ∂α = 0. Plugging the value of α for which ∂Hµ(ε,α) ∂α = 0 in H µ (ε, α), we get a polynomial of degree 2 in ε whose greatest root ε rips n (µ) gives the supremum of ε for which the above inequality holds. λ rips n (µ) = ε rips n (µ) R and letting α rips n (µ) be the value of α for which H µ (ε rips n (µ), α) = 0, we get the following reconstruction theorem: Theorem 14. Consider a finite set of points P and a compact subset X whose µ-reach R is positive. If d H (P, X) ≤ ε < λ rips n (µ) R then R(P, α rips n (µ)) is homotopy equivalent to X η for all η ∈ (0, R). Using a computer algebra system, we obtain

λ rips n (µ) = (2 -ϑ n )(2 + 2 √ 2 -ϑ n ) 2 -µ -µ 2 -4 + 2 √ 2 - √ 2ϑ n 1 + µ -µ 2 µ(2 -µ)(12 + 8 √ 2 -4ϑ n -4ϑ n √ 2 + (ϑ n ) 2 ) .
Plotting λ rips n (µ) as a function of µ, we observe that the ratio is only positive on a subinterval (µ * n , 1] of (0, 1]; see Figure 9(a). Hence, we can only guarantee that Rips complexes provide a reconstruction for shapes with a positive µ-reach when µ > µ * n . In Figure 9(b), we plotted µ * n as a function of n. µ * n increases with n and we were able to prove using a computer algebra system that µ * n tends to 2 √ 2 -2 ≈ 0.91 as n → +∞. In Figure 9(c), we plotted λ rips n (1) as a function of n. It decreases with n and similarly, we proved that lim n→+∞ λ rips n

(1) = 2 √ 2- √ 2- √ 2 2+ √ 2
≈ 0.034 and

lim n→+∞ α rips n (1) R = 1 - √ 2 2 + 1 -3 √ 2 4
2 -√ 2 ≈ 0.25.

Conclusion

Our work shows that Rips complexes can indeed provide topologically correct approximations of shapes.

An appealing aspect of Rips complexes is that they can be defined in metric spaces. Indeed, all we need is a notion of distances between points. Thus, it would be tempting to extend our results to metric spaces as well such as Riemannian manifolds, L p spaces or abstract metric spaces. A glance at the proof of our main result (Theorem 7) reveals the centrality of Jung's Theorem that relates the diameter and radius of any subset of an Euclidean space. A first step towards such an extension would be to replace Jung's theorem by an axiom in the considered metric space. For instance, in L ∞ spaces the diameter of a set is always twice its radius. Hence, Čech and Rips complexes coincide and Theorem 7 degenerates into a trivial form. Besides replacing Jung's theorem by an axiom, we would also need to adapt our definitions of convexity defects functions. The definition of c X is purely metric. The definition of h X requires, besides a metric, a notion of (local) convex hull which can be defined from geodesics for a large class of metric spaces (see the definition of complete length spaces in [START_REF] Gromov | Metric structures for Riemannian and non-Riemannian spaces[END_REF]).

Lemma 17 says that the hypotheses of Theorem 7 are stable under small metric perturbations. This seems to indicate that our relaxed definition of quasi Rips complexes (unlike the usual notion of Rips complexes) should allow us to apply Theorem 7 in the context of Gromov-Hausdorff distances.

Another natural extension would be to consider local measures of convexity defects and define sampling densities adapted to the local geometry of the sampled set in the spirit of [START_REF] Amenta | Surface reconstruction by Voronoi filtering[END_REF].

Acknowledgment

We gratefully acknowledge Xavier Goaoc and Martin Tancer for fruitful discussions.

Appendix C. Reconstructing shapes with a positive reach

In this appendix, we redo computations of Section 5.3, setting µ = 1, R = 1, n = +∞. That is, we consider a shape X whose reach is greater than or equal to 1 and a finite point set P such that d H (P, X) ≤ ε.

Reconstruction with the Čech complex. Combining Theorem 9 and Lemma 12, we get that the Čech complex C(P, α) is homotopy equivalent to X η for 0 < η < 1 whenever

1 - √ 1 -t 2 < t -3ε, ∀t ∈ [α + ε, α + 3ε]
which can be rewritten as This condition holds whenever the absolute difference between the two roots t 1 (ε) ≤ t 2 (ε) of the polynomial in t is greater than 2ε, that is, whenever 0 > 13ε 2 + 6ε -1. The supremum of ε for which the previous equation holds is λ cech (1) = -3+ √ 22 13 ≈ 0.13. For ε < λ cech (1), the admissible values of α range in the interval I 1 (ε) = [t 1 (ε)ε, t 2 (ε) -3ε]. Plugging the expression of the roots into the two endpoints of the interval, we get

I 1 (ε) = [ 1 2 + ε - √ 1 -6ε -9ε 2 2 , 1 2 - 3ε 2 + √ 1 -6ε -9ε 2 2 ].
Note that when epsilon tends to λ cech (1), the interval I 1 (ε) tends to the singleton 8 13 -√ 22 26 ≈ 0.44. Reconstruction with the Rips complex. Combining Theorem 10 and Lemma 12, we get that the Rips complex R(P, α) is homotopy equivalent to X η for all 0 < η < R whenever

1 -1 -( √ 2α + ε) 2 < 2α - √ 2α -2ε.
which we can rewrote as The left side is a polynomial of degree 2 in ε whose greatest root ε rips +∞ (1) =

2 √ 2- √ 2- √ 2 2+
√ 2 ≈ 0.034 gives the supremum of ε for which the above inequality holds. The corresponding value of α is

α rips +∞ (1) = 1 - √ 2 2 + 1 - 3 √ 2 4
2 -√ 2 ≈ 0.25.

Figure 2 :

 2 Figure 2: Smallest offset of X containing Centers(X, t) on the left and Hull(X, t) on the right.

Figure 3 :

 3 Figure 3: Notation for the proof of Lemma 1.

Figure 4 :

 4 Figure 4: The black points are the critical points of the curve X.

Figure 5 :

 5 Figure 5: Left: In a classical collapse, the link of σ has a unique inclusion-maximal simplex γ. Equivalently, the star of σ has a unique inclusion-maximal simplex σ ∪ γ different from σ. Right: In an extended collapse, the link of σ is a cone with apex o.

Figure 8 :

 8 Figure 8: Notation for the proofs of Lemma 11 on the left and Lemma 12 on the right.

2t 2 -

 2 2t(1 + 3ε) + 9ε 2 + 6ε < 0, ∀t ∈ [α + ε, α + 3ε].

5ε 2 + 4

 24 Since we are looking for the greatest value of ε for which the above equation holds, we may assume that the partial derivative of the left side with respect to α vanishes, which gives 4

  . . , p k } belongs to the Čech complex if and only if the k + 1 closed Euclidean balls B(p i , t) have non-empty common intersection. Let Nrv F = {G ⊂ F | G = ∅} denote the nerve of the collection F . The Čech complex is the nerve of the collection of balls {B(p, t) | p ∈ P }. Since balls are convex, the Nerve Lemma[START_REF] Bjorner | Topological methods[END_REF][START_REF] Edelsbrunner | Triangulating topological spaces[END_REF] implies that the Čech complex C(P, t) is homotopy equivalent to the union of these balls, that is, |C(P, t)| ≃ P t = p∈P B(p, t).

  Figure 10: Various point sets P on the left and corresponding convexity defects function c P on the right.

							1.8
							1.6
							1.4
							1.2
							1
							0.8
							0.6
							0.4
							0.2
							0	0	0.2	0.4	0.6	0.8	t	1	1.2	1.4	1.6	1.8
							1.2
							1
							0.8
							0.6
							0.4
							0.2
	2.8						0.45 0	0	0.2		0.4		0.6 t		0.8	1		1.2
	2.6						0.4
	2.4						0.35
	2.2						0.3
	2						0.25
	1.8						0.2
	1.6						0.15
							0.1
							0.05
	1.2 1.4	1.6 1.8	2	2.2 2.4 2.6 2.8	3	3.2	0	0	0.05	0.1	0.15	0.2	t	0.25	0.3	0.35	0.4	0.45

Diam(σ) for all dimensions n.

$ This work is partially supported by ANR Project GIGA ANR-09-BLAN-0331-01.

Appendix A. Smallest enclosing balls

In this appendix, we establish the existence and uniqueness of the smallest ball enclosing a non-empty bounded set σ of R n . We then prove that the radius and center of this smallest enclosing ball are stable under perturbation of σ.

Lemma 15. The smallest ball enclosing a non-empty bounded set of R n exists and is unique.

Proof. Let σ be a non-empty bounded set of R n . We first establish the existence of a smallest ball enclosing σ. Given a point y ∈ R n and a real number s ≥ 0, we first prove that the set B(y, s) of closed balls passing through y and with radius s or less is compact. Indeed, representing a closed ball with center z and radius r by point (z, r) in R n+1 , we can write

which is closed by definition and bounded since for all balls (z 0 , r 0 ) and (z 1 , r 1 ) in B(y, s), we have z 0z 1 + |r 0r 1 | ≤ 3s. The set of closed balls containing σ and whose radii are smaller than or equal to the diameter of σ is

This set is non-empty and compact and therefore, the continuous map (z, r) → r on B(σ) is bounded below and attains its infimum. The uniqueness is easy to establish by contradiction, as explained in [START_REF] Welzl | Smallest enclosing disks (balls and ellipsoids)[END_REF].

Lemma 16. For every non-empty bounded subsets σ and σ

Proof. Writing B for the smallest ball enclosing σ, we have ball as σ. Thus, z ∈ Hull(ξ) and the closed half-space H + that H bounds and which avoids z ′ intersects ξ. Let p be a point in this intersection. By choice of p in H + , the triangle pzz ′ is obtuse at vertex z and z ′ -

Interchanging the roles of σ and σ ′ yields:

Note that (r ′ + ε) 2r 2 ≤ (r + ε) 2r ′2 if and only if r ≥ r ′ . Considering in turn each of the two cases r ≤ r ′ and r ′ ≤ r, we get the desired inequality.

Appendix B. Hypotheses of Theorem 7 are stable

In this appendix, we establish the stability of hypotheses of Theorem 7 under small perturbations of the point set P . Given a point set P ⊂ R n , we say that a map f : P → R n is an ε-small perturbation of P if f is injective and pf (p) ≤ ε for all points p ∈ P . Given a simplicial complex K, we define the simplicial complex

and suppose moreover that α is an inert value of P . Then, there exist ε > 0 and β ′ > β such that for all ε-small perturbations f of P , we have:

Proof. Let us establish (i). For this, set t = ϑ n β and define t = min{Rad(σ) | ∅ = σ ⊂ P and Rad(σ) > t}. By construction, t > t. Lemma 4 ensures that for all subsets P ′ ⊂ R n within Hausdorff distance ε from P and for all t ′ ≥ 0, the following implication holds:

By assumption, we have 2αtc P (t) > 0. By choosing ε > 0 small enough, we can always find t ′ > t such that (1)

2

. Since c P (t ′ + ε) = c P (t), it follows that

and (i) is proved with β ′ = t ′ / ϑ n . By choosing ε > 0 small enough, we can always assume that in addition to conditions (1), ( 2) and (3), we have (4) ε < β ′β and ( 5) Rad(σ) / ∈ [αε, α + ε] for all ∅ = σ ⊂ P . Let f be an ε-small perturbation of P . Using Lemma 16 and condition (5), we get

. Consider a graph G whose flag complex is an (α, β)-quasi complex and let p and q be two points of P such that f (p)f (q) ≤ 2α.

We have pq ≤ 2α + 2ε and therefore using condition (5) pq ≤ 2α. It follows that the edge {p, q} belongs to G and consequently the edge {f (p), f (q)} belongs to f (G). Similarly, suppose f (p)f (q) > 2β ′ . This implies that pq > 2β ′ -2ε > 2β by condition (4) and therefore the edge {p, q} does not belong to G. Hence, the edge {f (p), f (q)} does not belong to f (G), showing (iii).