Cyrine Annabi

Florence Fourcade

Isabelle Soutrel

Florence Geneste

Didier Floner

Nizar Bellakhal

Abdeltif Amrane

Degradation of enoxacin antibiotic by the electro-Fenton process: Optimization, biodegradability improvement and degradation mechanism

Keywords: Electro-Fenton process,  Enoxacin removal,  Hydroxyl radicals,  Biodegradability improvement,  By-products

published or not. The documents may come

Degradation of enoxacin antibiotic by the electro-Fenton process: Optimization, biodegradability improvement and degradation mechanism

Introduction

In recent years, treating environmental hazards due to the significant detection of pharmaceutical compounds in wastewater became an area of interest for the scientific community worldwide [START_REF] Ellis | Pharmaceutical and personal care products (PPCPs) in urban receiving waters[END_REF][START_REF] Sui | Seasonal variation in the occurrence and removal of pharmaceuticals and personal care products in different biological wastewater treatment processes[END_REF][START_REF] Yoon | Occurrence of endocrine disrupting compounds, pharmaceuticals, and personal care products in the Han river (Seoul, South Korea)[END_REF]. Excretion after administration and wastes in the production sites are the main causes of the presence of pharmaceutical compounds in the aquatic environment [START_REF] Bound | Household disposal of pharmaceuticals as a pathway for aquatic contamination in the United Kingdom[END_REF]. This type of compounds has been recently classified as a priority risk pollutants [START_REF] Hernando | Environmental risk assessment of pharmaceutical residues in wastewater effluents, surface waters and sediments[END_REF][START_REF] Watkinson | The occurrence of antibiotics in an urban watershed: from wastewater to drinking water[END_REF]. Most of them are antibiotics. Their presence in wastewater is responsible for the development of antimicrobial resistance among microorganisms [START_REF] Levy | The challenge of antibiotic resistance[END_REF]. Owing to their recalcitrance, the commonly employed treatment processes (biological processes) appear not effective enough for a complete removal of such species. The contamination by these micropollutants is observed not only in the received water but reached also surface waters. Their toxic and adverse effects were proven in previous studies [START_REF] Daughton | Pharmaceutical and personal care products in the environment: agents of subtle change ?[END_REF][START_REF] Daughton | Pharmaceutical and personal care products in the environment: agents of subtle change ?[END_REF][START_REF] Giger | Occurrence and fate of antibiotics as trace contaminants in wastewaters, sewage sludges, and surface waters[END_REF].

Fluoroquinolones (FQs) are the third largest group of antibiotics with 17% of the global market share [START_REF] Van Doorslaer | Fluoroquinolone antibiotics : an emerging class of environmental micropolluants[END_REF]. They are frequently detected with relatively high concentrations in hospital wastewaters (3 ng L -1 -240 μg L -1 ), urban wastewaters (2 ng L -1 -14 μg L -1 ) and in bulk drug producer wastewaters (6 ng L -1 -31 mg L -1 [START_REF] Golet | Environmental exposure and risk assessment of fluoroquinolone antibacterial agents in wastewater and river water of the Glatt Valley Watershed, Switzerland[END_REF][START_REF] Lin | Pharmaceutical contamination in residential, industrial, and agricultural waste streams: risk to aqueous environments in Taiwan[END_REF][START_REF] Van Doorslaer | Fluoroquinolone antibiotics : an emerging class of environmental micropolluants[END_REF]. FQs are also observed in livestock and aquaculture wastewaters [START_REF] Van Doorslaer | Fluoroquinolone antibiotics : an emerging class of environmental micropolluants[END_REF]. Their broad antimicrobial spectrum may lead to the proliferation of bacterial drug resistance [START_REF] Watkinson | Removal of antibiotics in conventional and advanced wastewater treatment: implications for environmental discharge and wastewater recycling[END_REF]. FQs are characterized by their chemical stability and their high resistance to hydrolysis and to high temperatures, due to their quinolone ring. Conventional water treatment plants show a high variation in FQ removal efficiency (between 47 and 77% on average) [START_REF] Van Doorslaer | Fluoroquinolone antibiotics : an emerging class of environmental micropolluants[END_REF]. However, it is suggested by several authors that the predominant removal mechanism for FQ compounds is sorption to activated sludge rather than biodegradation [START_REF] Hendricks | The effectiveness of sewage treatment processes to remove faecal pathogens and antibiotic residues[END_REF][START_REF] Lindberg | Behavior of fluoroquinolones and trimethoprim during mechanical, chemical and active sludge treatment of sewage water and digestion of sludge[END_REF][START_REF] Van Doorslaer | Fluoroquinolone antibiotics : an emerging class of environmental micropolluants[END_REF]. A previous study reported that more than 80% of the total amount of ciprofloxacin and norfloxacin (FQ molecules) treated in a sewage treatment plant in Sweden was ultimately found in the digested sludge [START_REF] Lindberg | Behavior of fluoroquinolones and trimethoprim during mechanical, chemical and active sludge treatment of sewage water and digestion of sludge[END_REF]. This behavior is due to the high affinity of FQs for sludge, soils and sediments, through electrostatic and hydrophobic interactions [START_REF] Lindberg | Behavior of fluoroquinolones and trimethoprim during mechanical, chemical and active sludge treatment of sewage water and digestion of sludge[END_REF].

Therefore, an effective strategy must be found to degrade these compounds from aquatic matrices and to enhance their biodegradability as a pretreatment before their discharge into sewage treatment plants.

Advanced Oxidation Processes (AOP) have received great interest in recent years as an alternative method to treat organic and recalcitrant molecules [START_REF] Nasuhoglu | Removal of the antibiotic levofloxacin (LEVO) in water by ozonation and TiO2 photocatalysis[END_REF]. Some recent review papers reported the relevance of AOP on the degradation and the mineralization of residual molecules [START_REF] Feng | Removal of residual anti-inflammatory and analgesic pharmaceuticals from aqueous systems by electrochemical advanced oxidation processes[END_REF][START_REF] Klavarioti | Review article removal of residual pharmaceuticals from aqueous systems by advanced oxidation processes[END_REF][START_REF] Pera-Titus | Degradation of chlorophenols by means of advanced oxidation processes: a general review[END_REF]and Sirés et al., 2014). These oxidative treatment processes can be classified into four categories: chemical oxidation processes in homogeneous phase (H 2 O 2 /Fe(II) and H 2 O 2 /O 3 ); photocatalytic processes in homogeneous phase and/or heterogeneous phase (H 2 O 2 /UV, O 3 /UV, Fe(II)/H 2 O 2 /UV and TiO 2 /UV); oxidation by sonochemical processes and electrochemical oxidation processes. AOP are characterized by the in-situ production of hydroxyl radicals (OH) that are very strong oxidants (E° (OH/H 2 O) = 2.81 V/SHE at 25 °C) able to oxidize complex organic molecules such as pesticides [START_REF] Guivarch | Removal of organophosphorus pesticides from water by electrogenerated Fenton's reagent[END_REF], industrial dyes [START_REF] Hammami | Degradation of acid orang 7 by electrochemically generated OH radicals in acidic aqueous medium using a boron-doped diamond or platinum anode: a mechanistic study[END_REF] and pharmaceuticals [START_REF] An | Kinetics and mechanism of advanced oxidation processes (AOPs) in degradation of ciprofloxacin in water[END_REF][START_REF] Guinea | Degradation of the fluoroquinolone enrofloxacin by electrochemical advanced oxidation processes based on hydrogen peroxide electrogeneration[END_REF][START_REF] Ikehata | Degradation of aqueous pharmaceuticals by ozonation and advanced oxidation processes : a review[END_REF][START_REF] Mansour | Biodegradability improvement of sulfamethazine solutions by means of an electro-Fenton process[END_REF][START_REF] Rodrigues-Silva | Degradation of flumequine by photocatalysis and evaluation of antimicrobial activity[END_REF].

The electro-Fenton Process (EF) is one of the most efficient electrochemical AOP, which consists in the continuous production of hydroxyl radicals using electrogenerated Fenton reagent (H 2 O 2 /Fe(II)) according to the reactions below [START_REF] El-Desoky | Oxidation of Levafix CA reactive azo-dyes in industrial wastewater of textile dyeing by electro-generated Fenton's reagent[END_REF][START_REF] Xie | Interactive oxidation of photoelectrocatalysis and electro-Fenton for azo dye degradation using TiO2-Ti mesh and reticulated vitreous carbon electrodes[END_REF][START_REF] Xie | Interactive oxidation of photoelectrocatalysis and electro-Fenton for azo dye degradation using TiO2-Ti mesh and reticulated vitreous carbon electrodes[END_REF]:

O 2 +2H + +2e -→H 2 O 2 O2+2H++2e-→H2O2 H 2 O 2 +Fe 2+ →Fe 3+ +OH -+OHH2O2+Fe2+→Fe3++OH-+OH Fe 3+ +1e -→Fe 2+ Fe3++1e-→Fe2+
EF achieves high reaction yields and may be considered as an environmentally clean process [START_REF] El-Desoky | Oxidation of Levafix CA reactive azo-dyes in industrial wastewater of textile dyeing by electro-generated Fenton's reagent[END_REF].

Studies dealing with FQ degradation using AOP are numerous. Flumequine degradation was investigated by EF and by photo-electro-Fenton (PEF) in a non divided electrochemical cell using a Carbon-PTFE-air diffusion cathode and a Boron Doped Diamond (BDD) anode. Results showed an almost total mineralization in 360 min at 300 mA current intensity for both EF and PEF (Garcia-Segura et al., 2012). Ciprofloxacin was completely degraded by EF within 8 min and reached 94% of mineralization after 360 min of treatment using a carbon felt cathode and Platinum (Pt) anode [START_REF] Yahya | Oxidative degradation study on antimicrobial agent ciprofloxacin by electro-Fenton process : kinetics and oxidation products[END_REF]. Its degradation was also studied by sonochemistry [START_REF] Xiao | Sonochemical degradation of ciprofloxacin and ibuprofen in the presence of matrix organic compounds[END_REF]. Anodic oxidation and Solar-photo-electro-Fenton have been tested for Enrofloxacin elimination in an undivided filter press coupled to a photoreactor and using a batch recirculation flow plant. Investigations reported 28% and 86% of mineralization yields respectively after 300 min of treatment with a BDD anode and a Carbon PTFE gas diffusion cathode [START_REF] Guinea | Degradation of the fluoroquinolone enrofloxacin by electrochemical advanced oxidation processes based on hydrogen peroxide electrogeneration[END_REF]. Nasuhoglu et al. demonstrated the efficiency of ozonation and TiO 2 photocatalysis to degrade Levofloxacin leading to maximal oxidation yields of 59% and 70% respectively after 300 min of treatment [START_REF] Nasuhoglu | Removal of the antibiotic levofloxacin (LEVO) in water by ozonation and TiO2 photocatalysis[END_REF]. The efficiency of photocatalysis was also verified for moxifloxacin [START_REF] Van Doorslaer | Heterogeneous photocatalysis of moxifloxacin in water : chemical transformation and ecotoxicity[END_REF].

However, there is a lack of studies dealing with the effectiveness of coupling AOP with a biological treatment for FQs. The effectiveness of this type of coupling has been proven with other classes of antibiotics such as sulfonamides (sulfamethazine) [START_REF] Mansour | Biodegradability improvement of sulfamethazine solutions by means of an electro-Fenton process[END_REF], macrolides (tylosin) [START_REF] Yahiat | Removal of antibiotics integrated process coupling photocatalysis and biological treatment-case of tetracycline and tylosin[END_REF] and tetracycline [START_REF] Ferrag-Siagh | Tetracycline degradation and mineralization by the coupling of an electro-Fenton pretreatment and a biological process[END_REF].

Therefore, the focus of this study is to evaluate the applicability of EF for the pretreatment of enoxacin (ENO), an oral broad-spectrum FQ antibacterial agent, used in the treatment of respiratory and urinary tract infections [START_REF] Patel | Enoxacin: a reappraisal of its clinical efficacy in the treatment of genitourinary tract infections[END_REF] and to assess the possibility of coupling EF and a biological process for enoxacin mineralization. In this sense, the biodegradability of the degraded solution was examined. By-products and inorganic species were analyzed as well.

Materials and methods

Chemicals

Enoxacin (1-ethyl-6-fluoro-4-oxo-7-(piperazin-1-yl)-1,4-dihydro-1,8-naphthyridine-3carboxylic acid) was generously provided by the LNCM (Laboratoire National de Contrôle des Médicaments -Tunis, Tunisia) (structure displayed in Fig. 1). FeSO 4 •7H 2 O (purity 99%) and Na 2 SO 4 (purity 99%) were used as catalyst and a supporting electrolyte respectively and were purchased from Acros Organics (Thermo Fisher Scientific, Illkirch, France). Acetonitrile (purity 99.9%) (HPLC grade) was obtained from Sigma-Aldrich (Saint Quentin Fallavier, France). The initial pH of the solutions was adjusted to 3, the optimal pH value for the electro-Fenton process [START_REF] Diagne | Removal of methyl parathion from water by electrochemically generated Fenton's reagent[END_REF], by adding analytical grade sulfuric acid H 2 SO 4 purchased from Acros Organics. All solutions were prepared with ultrapure water and all the other chemicals used for analysis were supplied from Acros Organics and Sigma Aldrich.

Electrochemical apparatus and procedures

Experiments were performed at room temperature (18 °C) with an undivided cylindrical glass cell containing 250 mL of solution. The cell was equipped with two electrodes, a tridimensional carbon felt piece (Carbone Lorraine RVG 4000 Mersen, Paris La Défense, France) as cathode (90 mm × 50 mm × 12 mm) and a cylindrical platinum (Pt) electrode (34.6 cm 2 ) as anode, located in the center of the electrochemical reactor to have a good potential distribution. Compressed air was bubbled for 10 min through the cell to saturate the solution prior to electrolysis. The treated solutions contained a catalytic quantity of FeSO 4 .7H 2 O and their pH was adjusted to 3. Electrolyzes were carried out under current controlled conditions. The current was kept at the desired level with a DC power supply (Metrix, model AX 322-Chauvin Arnoux Group, Paris, France) operating in galvanostatic mode to control the current intensity. The ionic strength was maintained constant with the addition of 50 mmol L -1 Na 2 SO 4 .

Analytical procedure

Electrochemical analysis

Electrochemical analysis of ENO was performed using a conventional three-electrodes cell with a vitreous carbon disk electrode (3.14 mm 2 ) as the working electrode and a Pt wire as the counter electrode. All the electrode potentials were measured with respect to an Ag/AgCl electrode located near to the working electrode. Experiments were performed at ambient temperature under nitrogen atmosphere to avoid dissolved oxygen. Voltammograms were obtained with a scan rate of 20 mV s -1 using a BioLogic SP-150 potentiostat recorded to EC-Lab V10.36 software.

High performance liquid chromatography (HPLC)

The evolution of ENO concentrations was monitored by HPLC using a Waters 996 system equipped with Waters 996 PDA (Photodiode Array Detector) and Waters 600LCD Pump. The separation was achieved on a Waters C-18, (5 μm; 4.6 × 250 mm) reversed-phase. Analyses were carried out isocratically using a mixture of acetonitrile/MilliQ water (10/90, v/v) with 0.1% formic acid as eluent, at a flow rate of 1 mL min -1 . Detection of ENO was performed at 270 nm and the retention time was approximately 12 min.

Total organic carbon (TOC) and total nitrogen (TN) measurements

TOC and TN were measured by means of a TOC-V CPH/CPG Total Organic Analyzer Schimadzu. Organic Carbon compounds were combusted and converted to CO 2 which was detected by a non-dispersive Infra-Red Detector (NDIR). Dissolved Nitrogen compounds were combusted and converted to NO which was then mixed with Ozone chemiluminescence for detection by a photomultiplier.

Chemical oxygen demand (COD) measurements

COD was measured by means of a Test Nanocolor ® CSB 40 and 160 from Macherey-Nagel (Düren, Germany) [START_REF] Mansour | Biodegradability improvement of sulfamethazine solutions by means of an electro-Fenton process[END_REF].

Biochemical oxygen demand (BOD 5 ) measurements

BOD 5 measurements were carried out in Oxitop IS6 (from WTW) in order to evaluate the biodegradability for ENO molecule and its by-products. Inoculation of samples, blank solution and control solution was performed according to the following procedure: 100 g of activated sludge (collected from a local wastewater treatment plant) was mixed in distilled water; after agitation the solution was left stand for 10 min; and 20 mL of supernatant was then harvested and mixed to distilled water to obtain a total volume of 2 L. The following mineral basis was used for all experiments (g L -1 ): MgSO 4 •7H 2 O, 22.5; CaCl 2 , 27.5; FeCl 3 , 0.15; NH 4 Cl, 2.0; Na 2 HPO 4 , 6.80; KH 2 PO 4 , 2.80. The BOD 5 value was initially estimated based on the COD value experimentally measured or calculated, BOD 5 = COD/1.46.

Neutral pH (7.0 ± 0.2) was adjusted for all the samples by adding NaOH [START_REF] Chebli | Supported photocatalysis as a pre-treatment prior to biological degradation for the removal of some dyes from aqueous solutions ; acid red 183, Biebrich scarlet, methyl red sodium salt, orange II[END_REF].

Inorganic ions quantification

The monitoring of ammonium species (NH 4 + ) was realized via the spectrophotometric method of Nessler at 420 nm [START_REF] Rodier | L'analyse de l'eau : eaux naturelles, eaux r esiduaires, eau de mer[END_REF]. Fluorides were quantified according to the standard additions method, using a specific fluoride electrode [START_REF] Yam | D etermination de la dose optimale de fluor dans l'eau de boisson au S enegal[END_REF]. Nitrate and Nitrite ions monitoring was carried out by a spectrophotometric method at 415 nm and 543 nm, respectively [START_REF] Rodier | L'analyse de l'eau : eaux naturelles, eaux r esiduaires, eau de mer[END_REF].

Liquid chromatography-mass spectrometry (UPLC-MS/MS)

The devices used are detailed in a previous work [START_REF] Assassi | Combined electrochemical and biological treatment for pesticide degradation -Application to phosmet[END_REF]. The analytes were separated by a Waters Acquity UPLC system (Waters Corporation, Milford, MA, USA) consisting of an Acquity UPLC binary solvent manager, an Acquity UPLC sample manager and an Acquity UPLC column heater equipped with a Waters Acquity UPLC BEH Shield RP18 column (2.1 mm × 100 mm, 1.7 μm particle size) (Milford, MA, USA) maintained at 45 °C. Analyses were performed using 0.1% formic acid in acetonitrile as eluent A and 0.1% formic acid in a mixture of MilliQ Water/Acetonitrile (90/10, v/v) as eluent B, delivered at a flow rate of 0.4 mL min -1 .

The elution gradient started with 0% of eluent A and increased linearly to 100% of A within 5 min.

The separated compounds were detected with a Waters Micromass Quattro Premier (Waters Corporation, Manchester, UK) triple quadruple mass spectrometer. It was operating with an electrospray source in positive ionization mode with a cone potential of 30 V. The ionization source conditions were: capillary voltage of 3.0 kV and source temperature of 350 °C. The cone and desolvation gas flows were 50 L h -1 and 750 L h -1 , respectively. They were obtained from an in-house nitrogen source, the Peak Scientific NM30LA (Peak Scientific, Inchinann, United Kingdom). High-purity argon (99.99%, Air Liquid, Paris, France) was used as collision gas and was regulated at 0.1 mL min -1 . Analyses were performed in full scan and daughter scan modes, with a collision energy of 25 eV. Spectra were acquired between 80 and 500 mz -1 and the data were treated with Micromass Mass-Lynx 4.1 software.

Ionic chromatography (CI)

Generated carboxylic acids were identified by DIONEX DX120 ion chromatography equipped with a conductivity detector, using an anion exchange column AS19 (4 × 250 mm) as the stationary phase, and a solution of KOH in water as the mobile phase. The analyses were carried out with a gradient elution mode. It started with 10 mmol L -1 of KOH during 10 min then increased linearly to 45 mmol L -1 from 10 to 25 min and finished with 45 mmol L -1 of KOH from 25 to 35 min. The flow rate was set at 1 mL min -1 [START_REF] Yahiat | Removal of antibiotics integrated process coupling photocatalysis and biological treatment-case of tetracycline and tylosin[END_REF].

Results and discussion

Electrochemical behavior of enoxacin

The electrochemical behavior of enoxacin was studied in order to conclude on the contribution of a direct oxidation and/or reduction of the target molecule at the electrode surface to the EF process. For this purpose, current potential curves were plotted by cyclic voltammetry in Na 2 SO 4 50 mmol L -1 supporting electrolyte at pH 3 with 500 mg L -1 of the target compound. In the presence of enoxacin, oxidation and reduction of water were shifted toward anodic and cathodic potentials, respectively. This potential shift was probably due to the adsorption of the target compound onto the electrode surface. A non reproducible signal in reduction was observed around -1.3 V/Ag/AgCl (Supplementary material 1) which indicated an irreversible electrochemical reaction and the influence of the adsorption of the antibiotic on the peak current. The irreversible reduction of ENO has already been observed and has been attributed to a two electrons reduction of the ketone group of the molecule [START_REF] Zhang | Electroanalytical characteristics of enoxacin and their analytical application[END_REF][START_REF] Zhou | Polarographic and voltammetric behaviour of enoxacin[END_REF].

The three amines groups were protonated at pH 3, thus no signal on their oxidation was observed on the voltammograms.

During the EF process, even if the ketone group was reduced by a direct two electrons transfer at the electrode interface, the formation of alcohol should not significantly enhance the biodegradability of the molecule.

Effect of the operating parameters on enoxacin degradation by EF

The decrease of the ENO concentration during the EF was monitored and different operating conditions were examined, including the initial concentration of ENO, the initial Fe(II) concentration and the applied current intensity.

Effect of the initial enoxacin concentration

The electrolysis was carried out at 200 mA, with 0.2 mmol L -1 Fe(II) and with initial amounts of ENO in the range of 50-200 mg L -1 (Fig. 2). The results show a clear impact of the initial ENO amount on the degradation efficiency, especially between 100 and 200 mg L -1 (Fig. 2); while almost similar final degradation yields can be observed after 60 min (Fig. 2). This trend can be explained by an increase of organic molecules in the solution which requires a greater number of hydroxyl radicals to their degradation (Sirés et al., 2007a). Experimental kinetics can be satisfactorily described by a pseudo-first order reaction kinetic (inset of Fig. 2). The apparent kinetic rate constant values (k app ) for the oxidation of ENO correspond to the slopes of the linear fits of the plots of ln([ENO] 0 /[ENO]) versus time (Table 1). The decrease of k app can most likely be attributed to the gradual acceleration of competitive reactions between hydroxyl radicals and the oxidation intermediates of ENO that were formed during the process [START_REF] Flox | Mineralization of herbicide mecoprop by photoelectro-Fenton with UVA and solar light[END_REF]Sirés et al., 2007a). Furthermore, even if the amount of ENO increased in solution, the number of OH produced remained constant. As a consequence, hydroxyl radicals were the limiting reagent of the degradation of ENO [START_REF] Flox | Electro-Fenton and photoelectron-Fenton degradation of indigo carmine in acidic aqueous medium[END_REF]

Effect of the Fe(II) concentration

The effect of Fe(II) on the degradation of the target molecule was investigated in the presence of 50 mg L -1 of ENO and for an applied constant current intensity of 200 mA. The ENO degradation yields increased with increasing Fe(II) concentration from 0.1 to 0.2 mmol L -1 , while it decreased above 0.2 mmol L -1 (Fig. 3). On the one hand, the increase of the degradation efficiency observed between 0.1 and 0.2 mmol L -1 can be attributed to the higher production of hydroxyl radicals for increasing amount of Fe(II), according to the Fenton reaction (2) [START_REF] Panizza | Electro-Fenton degradation of synthetic dyes[END_REF]. On the other hand, the negative effect of the Fe(II) amount beyond 0.2 mmol L -1 should be most likely attributed to a competitive reaction occurring between the hydroxyl radicals generated and the excess of ferrous ions according to the reaction (5) (Panizza and[START_REF] Panizza | Electro-Fenton degradation of synthetic dyes[END_REF][START_REF] Sun | Photochemical reactions involved in the total mineralization of 2,4-D by iron(3þ)/hydrogen peroxide/UV[END_REF][START_REF] Sun | Photochemical reactions involved in the total mineralization of 2,4-D by iron(3þ)/hydrogen peroxide/UV[END_REF]: The inset of the panel of Fig. 3 shows that experimental kinetics are well described by a pseudo-first order reaction rate. The values of the apparent rate constant k app presented the same evolution than the degradation efficiency, they increased with increasing Fe(II) concentration until 0.2 mmol L -1 of catalyst and decreased beyond this Fe(II) amount (Table 1). As a consequence and in order to reach optimal results, 0.2 mmol L -1 of Fe(II) was employed as a catalyst concentration in the rest of the electrolyzes performed in this study.

Fe 2+ +OH→Fe 3+ +OH -Fe2++OH→Fe3++OH-

Effect of the applied current intensity

The current intensity is a key parameter in the effectiveness of the EF process [START_REF] Oturan | Reaction sequence for the mineralization of the short-chain carboxylic acids usually formed upon cleavage of aromatics during electrochemical Fenton treatment[END_REF][START_REF] Ozcan | Removal of acid orange 7 from water by electrochemically generated Fenton's reagent[END_REF]. To investigate its effect, experiments were carried out for 50 mg L -1 ENO and 0.2 mmol L -1 of Fe(II) and current intensities varying in the range 50-300 mA. The obtained results show that an increase in the current intensity improved the ENO degradation yields, from 74% after 30 min of electrolysis at 50 mA to 91% for 300 mA (Fig. 4). The improvement appeared more significant at the examination of k app of the pseudofirst order kinetic model showing an increase from 0.048 min -1 to 0.094 min -1 for current intensities increasing from 50 to 300 mA (inset of Fig. 4 and Table 1). The increase of the degradation yield associated with the increase of the current intensity can be explained by an increase of hydrogen peroxide production (see Supplementary material 2) and an increase of the regeneration rate of Fe(II) at the cathode, leading to a higher amount of hydroxyl radicals produced [START_REF] Oturan | Reaction sequence for the mineralization of the short-chain carboxylic acids usually formed upon cleavage of aromatics during electrochemical Fenton treatment[END_REF][START_REF] Ozcan | Removal of acid orange 7 from water by electrochemically generated Fenton's reagent[END_REF]. Furthermore, the concentration of electrogenerated H 2 O 2 during electrolysis can decrease when the current intensity increase, since oxygen reduction can lead to water instead of H 2 O 2 at the cathode and owing to possible direct oxidation of H 2 O 2 in a monocompartment electrochemical cell at the anode [START_REF] Brillas | Electro-Fenton process and related electrochemical technologies based on Fenton's reaction chemistry[END_REF]. These assumptions can account for the very close results obtained at 200 mA and 300 mA (Fig. 4 and Table 1).

Results obtained at 50 and 100 mA were similar; no significant effect on enoxacin degradation was observed. The apparent kinetic constants (Table 1) were then similar (0.045 and 0.048 min -1 respectively).

Electro-Fenton efficiency on the mineralization of enoxacin

The above results have shown that the optimal conditions for the degradation of enoxacin by the electro-Fenton process were [ENO] 0 = 50 mg L -1 ; I = 300 mA and [Fe(II)] = 0.2 mmol L -1 . To complete the analysis of the impact of this process on enoxacin removal, mineralization and oxidation were also monitored and are shown in Fig. 5. TOC and COD followed similar trends to that of enoxacin degradation, since a significant decrease occurred within 30 min of electrolysis, reaching 26 and 49% decrease respectively (Fig. 5). Refractory organic by-products were most likely responsible of the low mineralization yield (Sirés et al., 2007b). From 60 min of treatment, an almost total enoxacin abatement was observed (97%), while mineralization and oxidation remained limited, 43 and 54% after 120 min, respectively (Fig. 5). The slight decrease of mineralization observed between 120 and 180 min of treatment has been previously attributed to the accumulation of organic recalcitrant aromatic rings [START_REF] Babic | Photolytic degradation of norfloxacin, enrofloxacin and ciprofloxacin in various aqueous media[END_REF]. Furthermore, the amount of OH produced may be insufficient to mineralize the molecule.

Enoxacin biodegradability study

The BOD 5 on COD ratio is a recognized indicator of the biodegradability of a solution; this ratio must be higher or equal to 0.4 to consider that the solution is easily biodegradable [START_REF] Salles | Relevance of an electrochemical process prior to a biological treatment for the removal of an organo-phosphorous pesticide, phosmet[END_REF]. As expected, enoxacin was not biodegradable before electrolysis (Fig. 6). Biodegradability increased after 60 min electrolysis at 300 mA, with a BOD 5 on COD ratio of 0.25, showing that primary by-products were relatively resistant to micro-organisms. However, a readily biodegradable solution, with a ratio of 0.51 was obtained after 180 min of electrolysis. It can be explained by the oxidation of the remaining recalcitrant by-products previously generated via the hydroxyl radicals [START_REF] Mansour | Biodegradability improvement of sulfamethazine solutions by means of an electro-Fenton process[END_REF]. However, for a longer electrolysis time, the obtained electrolyzed solution became less biodegradable since the BOD 5 on COD ratio decreased from 0.51 to 0.30 after 360 min, in agreement with the related literature [START_REF] Mousset | Treatment of synthetic soil washing solutions containing phenanthrene and cyclodextrin by electro-oxidation. Influence of anode materials on toxicity removal and biodegradability enhancement[END_REF], and which may be related to the accumulation of recalcitrant quinolone rings for increasing electrolysis time [START_REF] Babic | Photolytic degradation of norfloxacin, enrofloxacin and ciprofloxacin in various aqueous media[END_REF]. From this, the relevance of an EF pretreatment was confirmed and 180 min electrolysis of the ENO solution is required for an effective biological treatment. The relevance of the coupling of an EF pretreatment and a biological process can be also estimated from the examination of the evolution of the COD/TOC ratio, displayed in the inset of Fig. 6. A favorable trend is a decrease of this ratio [START_REF] Chebli | Supported photocatalysis as a pre-treatment prior to biological degradation for the removal of some dyes from aqueous solutions ; acid red 183, Biebrich scarlet, methyl red sodium salt, orange II[END_REF], which was experimentally observed after EF pretreatment. In accordance with the improvement of the solution's biodegradability, the COD/TOC ratio decreased from 2.40 for an untreated solution to 1.62 for 60 min of electrolysis. The ratio COD/TOC then slightly decreased to 1.51 after 180 min of treatment.

Evolution of the generated inorganic ions

The enoxacin molecule contains an atom of fluorine and three atoms of nitrogen. The progressive generation of inorganic ions such as fluorides F -, nitrates NO 3 -and ammonium NH 4 + was therefore not surprising (Fig. 7 (a)). However, no nitrite NO 2 -anions were detected. The mineralization of enoxacin was therefore accompanied by the conversion of its heteroatoms into inorganic ions [START_REF] El-Desoky | Oxidation of Levafix CA reactive azo-dyes in industrial wastewater of textile dyeing by electro-generated Fenton's reagent[END_REF]. Ammonium concentration increased progressively until reaching a constant value of 0.12 mmol L -1 after 120 min of treatment. Nitrates remained constant throughout the electrolysis and did not exceed 25 μmol L -1 . 24% of the nitrogen atoms of the target molecule were transformed into ammonium, while only 5% were transformed into nitrates after 120 min. The percentage of undetected nitrogen may be related to the presence of nitrogen in the degradation products, such as the stable Nderivatives found by LC-MS/MS [START_REF] Garcia-Segura | Mineralization of flumequine in acidic medium by electro-Fenton and photoelectro-Fenton processes[END_REF]. The fluorides amount increased continuously until the end of electrolysis, reaching a value of 0.12 mmol L -1 , namely 77% of the fluorine likely to be found after a total conversion (0.16 mmol L -1 ). The fluorine atoms unconverted into inorganic ions are likely to be included in the structure of some degradation by-products [START_REF] Babic | Photolytic degradation of norfloxacin, enrofloxacin and ciprofloxacin in various aqueous media[END_REF][START_REF] Garcia-Segura | Mineralization of flumequine in acidic medium by electro-Fenton and photoelectro-Fenton processes[END_REF].

Study of the generated carboxylic acids

The degradation of aromatics and heteroatoms by hydroxyl radicals involves the generation of short-linear aliphatic carboxylic acids, produced from the cleavage of their aromatic moieties and lateral groups [START_REF] Garcia-Segura | Mineralization of flumequine in acidic medium by electro-Fenton and photoelectro-Fenton processes[END_REF]. Based on this information, it can be noticed that the degradation of 50 mg L -1 of enoxacin by EF at 300 mA was also accompanied by the generation of several carboxylic acids. Three of them were identified by Ion Chromatography, presenting well defined peaks: formic (6.22 min), acetic (5.44 min) and oxalic (21.08 min) acids. A progressive increase of the acids concentration was observed during the course of electrolysis (Fig. 7 (b)), with the higher concentration (more than 3 mg L -1 ) observed for formic acid (C-1 acid) compared to acetic and oxalic acids (C-2 acid). It can be interpreted by the transformation of the C-2 acids into a C-1 acid, due to the hydroxyl radicals' attack [START_REF] Garcia-Segura | Mineralization of flumequine in acidic medium by electro-Fenton and photoelectro-Fenton processes[END_REF]. Note that oxalic and formic acids are ultimate carboxylic acids because they can be directly converted into CO 2 (Garcia-Segura and[START_REF] Garcia-Segura | Mineralization of the recalcitrant oxalic and oxamic acids by electrochemical advanced oxidation processes using a borondoped diamond anode[END_REF][START_REF] Oturan | Reaction sequence for the mineralization of the short-chain carboxylic acids usually formed upon cleavage of aromatics during electrochemical Fenton treatment[END_REF].

On the other hand, it has been reported that under EF conditions, carboxylic acids form complexes with Fe(III) present in the solution according to the Fenton reaction (reaction 3) [START_REF] Brillas | Electro-Fenton process and related electrochemical technologies based on Fenton's reaction chemistry[END_REF]. This can explain the behavior of formic and oxalic acids (Fig. 7 (b)), which were accumulated within the first 30 min of electrolysis, reaching a plateau after this time. To account for this trend, it can be assumed that they probably reacted with Fe(III) and then their complexes rapidly reacted with hydroxyl radicals (Garcia-Segura and [START_REF] Garcia-Segura | Mineralization of the recalcitrant oxalic and oxamic acids by electrochemical advanced oxidation processes using a borondoped diamond anode[END_REF]. In contrast, acetic acid was more recalcitrant and increased progressively, reaching 1.94 mg L -1 after 180 min of treatment.

The carboxylic acids accumulated at the end of the electrolysis were involved in the residual TOC displayed in Fig. 5 [START_REF] Garcia-Segura | Mineralization of flumequine in acidic medium by electro-Fenton and photoelectro-Fenton processes[END_REF].

Elucidation of by-products and mechanism of degradation

Based on the results of the UPLC-MS/MS analysis, four by-products were detected after 30 and 60 min of treatment (Table 2), which allowed to suggest a general pathway for ENO degradation by EF (Fig. 8). There is no literature dealing with the degradation pathway of enoxacin. The proposed mechanism of ENO degradation is based on the mass spectra of intermediates, on the molecular weight of ion fragments derived from each degradation product and on previous studies done on other FQs [START_REF] Babic | Photolytic degradation of norfloxacin, enrofloxacin and ciprofloxacin in various aqueous media[END_REF][START_REF] Dolar | Photolysis of enrofloxacin and removal of its photodegradation products from water by reverse osmosis and nanofiltration membranes[END_REF][START_REF] Sturini | Photolytic and photocatalytic degradation of fluoroquinolones in untreated river water under natural sunlight[END_REF].

For each molecular mass found, various structures were suggested. Indeed, inorganic species time courses showed only a partial generation of fluorides, nitrates and ammonium, and hence the presence of by-products with or without heteroatoms is possible. Moreover, after 30 min of treatment, 87% of ENO was removed, so that the hydroxyl radicals generated can attack the by-products, accounting for the presence of a significant amount of short carboxylic acids after 30 min of degradation (Fig. 7 (b)).

According to the literature, ENO may be first attacked on its piperazine ring, seeing that it is the most oxidable part of the molecule [START_REF] Babic | Photolytic degradation of norfloxacin, enrofloxacin and ciprofloxacin in various aqueous media[END_REF]. The structures of ENO I came principally from the opening of the piperazine ring and its transformation into two groups of amides [START_REF] Babic | Photolytic degradation of norfloxacin, enrofloxacin and ciprofloxacin in various aqueous media[END_REF]. It was made up of oxidative rearrangements on the N-ethyl piperazine chain. The N-ethyl substituent of the benzo ring may also be oxidized on aldehyde group (not shown).

The second step consisted in the elimination of an ethyl group from the N-ethyl substituent or the elimination of a carbon monoxyde (CO) molecule from one of the amide groups to obtain ENO II structures.

ENO III and ENO IV structures resulted from the successive elimination of an ethyl, a carbon monoxide and/or an ammonia molecule (NH 3 ), in order to obtain diverse possible byproducts, including a primary, a secondary or a tertiary amine in their structures [START_REF] Babic | Photolytic degradation of norfloxacin, enrofloxacin and ciprofloxacin in various aqueous media[END_REF][START_REF] Sturini | Photolytic and photocatalytic degradation of fluoroquinolones in untreated river water under natural sunlight[END_REF].

In accordance with older studies, all the intermediates suggested showed the persistence of the quinolone ring in their structures, which explain the high residual TOC and COD in the treated solution.

Short carboxylic acids generated during electrolysis may derive from ENO IV by-products [START_REF] Babic | Photolytic degradation of norfloxacin, enrofloxacin and ciprofloxacin in various aqueous media[END_REF][START_REF] Vasconcelos | Photo-degradation of the antimicrobial ciprofloxacin at high pH : identification and biodegradability assessment of the primary by-products[END_REF].

The nomenclature of enoxacin intermediates suggested in this study is given in supplementary material (Supplementary material 3).

Conclusion

The present paper proves the effectiveness of the electro-Fenton treatment for the remediation of the fluoroquinolone enoxacin present in wastewaters and in surface water. Around 98% degradation yield was obtained after 60 min of electrolysis in the optimal experimental conditions, namely 50 mg L -1 initial enoxacin amount, 300 mA and 0.2 mmol L -1 Fe(II). Furthermore, biodegradability was enhanced after 180 min of treatment with a maximum BOD 5 on COD ratio of 0.51; while TOC removal yield did not exceed 32% after this electrolysis time. It can be explained by the generation of recalcitrant by-products during electrolysis and the persistence of the quinolone ring. This behavior was confirmed by the primary products found during UPLC-MS/MS analyses.

After 180 min electrolysis of 50 mg L -1 ENO, 77% of the fluorine contained in the target compound was converted into fluorides. Moreover, the nitrogen content of ENO was partially converted to nitrate (5%) and ammonium (24%) ions. Oxalic, acetic and formic acids were also formed, which can be easily mineralized leading to CO 2 and H 2 O.

From the above results, EF is certainly suitable for the removal of ENO in wastewaters. It also presents a relevant solution and an effective pretreatment for the improvement of biodegradability. Further studies could be considered as a perspective in order to optimize the ideal electrolysis time for good biodegradability.

Appendix A. Supplementary data

Attached

Fig. 1 .

 1 Fig. 1. Molecular structure of enoxacin.

Fig. 2 .

 2 Fig. 2. Effect of the initial ENO concentration on its degradation and kinetic analysis for the pseudo first-order reaction of ENO. Experimental conditions: [Fe(II)] = 0.2 mmol L -1 , I = 200 mA, pH = 3, [Na 2 SO 4 ] = 50 mmol L -1 , V = 250 mL.

Fig. 3 .

 3 Fig. 3. Effect of Fe (II) concentration on ENO degradation and kinetic analysis for the pseudo first-order reaction of ENO. Experimental conditions: C 0 = 50 mg L -1 , I = 200 mA, pH = 3, [Na 2 SO 4 ] = 50 mmol L -1 , V = 250 mL.

Fig. 4 .

 4 Fig. 4. Effect of the applied current intensity on the ENO degradation and kinetic analysis for the pseudo first-order reaction of ENO. Experimental conditions: C 0 = 50 mg L -1 , [Fe(II)] = 0.2 mmol.L -1 ,pH = 3, [Na 2 SO 4 ] = 50 mmol L -1 , V = 250 mL.

Fig. 5 .

 5 Fig. 5. Time-course of ENO concentration, TOC and COD during ENO degradation by EF. Experimental conditions: C 0 = 50 mg L -1 , I = 300 mA, [Fe(II)] = 0.2 mM, pH = 3, [Na 2 SO 4 ] = 50 mmol L -1 , V = 250 mL.

Fig. 6 .

 6 Fig. 6. Evolution of the BOD 5 on COD ratio and the COD on TOC ratio during electrolysis. Experimental conditions: C 0 = 50 mg L -1 , I = 300 mA, [Fe(II)] = 0.2 mmol L -1 , pH = 3, [Na 2 SO 4 ] = 50 mmol L -1 , V = 250 mL.

Fig. 7 .

 7 Fig. 7. Time-course of the concentration of (a) inorganic species and (b) carboxylic acids during ENO degradation by EF. Experimental conditions: C 0 = 50 mg L -1 ; I = 300 mA, [Fe(II)] = 0.2 mmol L -1 ; [Na 2 SO 4 ] = 50 mmol L -1 ; t = 60 min, pH = 3, V = 250 mL.

Table 1 .

 1 .Apparent kinetic rate constants k app obtained during the EF treatment at various initial ENO concentrations, Fe(II) concentrations and applied current intensity.

	Initial ENO concentration (mg L -1 )	Fe(II) concentration (mmol L -1 )	Applied current intensity (mA)	Apparent kinetic rate constant k app (min -1 )
		0.2	200	0.082
		0.2	200	0.075
		0.2	200	0.075
		0.2	200	0.032
		0.1	200	0.055
		0.2	200	0.082
		0.5	200	0.049
		1	200	0.039
		0.2	50	0.045
		0.2	100	0.048
		0.2	200	0.082
		0.2	300	0.094

Table 2 .

 2 Intermediates products generated during the EF degradation of enoxacin.

Products Retention time (min) MH + (g mol -1 ) Ion fragments (g mol -1 )

	Products
			303
	Enoxacin 1.23	321	257 234
			206
			333
	ENO I 1.68	351	305 259
			232
			305
	ENO II 1.8	323	259
			232
			262
	ENO III 1.8	280	234
			206

Retention time (min) MH + (g mol -1 ) Ion fragments (g mol -1 )

			234
			206
	ENO IV 2.02	252	178
			150
			123
	Fig. 8.

Proposed structures for by-products of enoxacin EF degradation.


Francis Lazarus
email: lazarus@sic.univ-poitiers.fr

Anne Verroust
email: anne.verroust@inria.fr

Level Set Diagrams of Polyhedral Objects

Keywords: skeleton, cylindrical decomposition, Euler Formula, Dijkstra's algorithm

Shape descriptors and feature-based representations are of primary interests in the area of solid modeling. They allow us for easier storage, recognition and general treatments of objects. Axial structures such as skeletons are popular shape descriptors which have been widely studied. Most of the studies focus on a particular type of skeleton called the Medial Axis. Medial Axes can be extracted from discrete volumetric data as well as boundary-based representations. In the later case, however, no algorithm is known to perform well and accurately. We propose a new paradigm for constructing one dimensional axial structures associated with a polyhedral object. These structures, called the level set diagrams, are associated with scalar functions defined over the set of vertices of a polyhedron. We study in details the level set diagram associated with the shortest path distance to a source point. This particular association fits nicely into a theoretical framework and presents interesting properties for the purpose of shape description.

Introduction

We present a new paradigm for constructing one dimensional axial structures, the level set diagrams (LSDs for short), associated with a polyhedral object. These diagrams capture the overall shape as well as the topology of an object. They can be used for deforming or animating an object. This construction is radically different from the classical Medial Axis [START_REF] Blum | Shape description using weighted symmetric axis features[END_REF][START_REF] Leymarie | Snakes and skeletons[END_REF] dimensional structure. Formally, the Medial Axis is the set of the centers of maximal spheres contained in a given object. Algorithms that construct the Medial Axis of a polyhedral surface are generally complex. They start with adding points on the object boundary and computing their Delaunay triangulation [START_REF] Goldak | Constructing discrete medial axis of 3D objects[END_REF]. Generally, the resulting Medial Axis needs to be pruned as it may contains numerous small branches [START_REF] Attali | Computing and simplifying 2D and 3D semicontinuous skeletons of 2D and 3D shapes[END_REF]. Also, the Medial Axis can be composed of pieces of curves as well as pieces of surfaces. By construction, however, LSDs are simple one dimensional graphs. They relate to the level sets of scalar functions defined over the vertices of a polyhedral surface. More precisely, the points of an LSD correspond to "average points" associated with the connected components of the level sets of a given scalar function. Figure 1 shows an LSD of a threefingered shape.

Figure 1: An LSD (bold lines) of a an object is defined by the centers of the connected components of the level sets (thin lines) of a given function. The dashed bold lines indicate joints between LSD branches. Shinagawa et al. [START_REF] Shinagawa | Surface coding based on Morse theory[END_REF][START_REF] Takahashi | Algorithms for extracting correct critical points and constructing topological graphs from discrete geographical elevation data[END_REF] have introduced a similar diagram in the context of medical and geographical applications. They call their diagram the Reeb graph in reference to a classical topological graph associated with level sets of a Morse function 1 , f , defined on a smooth surface [START_REF] Milnor | Morse theory[END_REF][START_REF] Hart | Morse theory for implicit surface modeling[END_REF]. The vertices of the Reeb graph correspond to critical points of the function f , that is points where the gradient of f is null. Shinagawa et al. are mainly interested in encoding the topological structure of a terrain while the LSD is a geometrical skeleton that describes both the topology and the geometry of an object.

LSDs depend on the particular function chosen to compute the level sets. Shinagawa et al. use the height function (the zcoordinate), relatively to a given orientation of the object to define their diagram. This is particularly meaningful for terrain data as critical points correspond to peaks, pits or passes of the terrain. We show that in our case the shortest path distance to a source point is often a better choice of function especially for describing the geometry of tubular and branching objects.

The two major components of our approach are the study of the level sets of a function defined on a polyhedron and the use of the shortest path distance to a source point to define such a function. de Berg et van Kreveld [START_REF] Berg | Trekking the alps without freezing or getting tired[END_REF] studied the structure of the level sets of the height function on a polyhedral terrain. As in [START_REF] Shinagawa | Surface coding based on Morse theory[END_REF][START_REF] Takahashi | Algorithms for extracting correct critical points and constructing topological graphs from discrete geographical elevation data[END_REF], the structure of the level sets is recorded into a tree analogous to the Reeb graph. In [START_REF] Berg | Trekking the alps without freezing or getting tired[END_REF], it is shown that this tree, called the contour tree, can be constructed in O(n log n) time.

In [START_REF] Van Kreveld | Contour trees and small seed sets for isosurface traversal[END_REF], a simpler construction of the contour tree is provided for general functions (not only height functions) defined on general polyhedra (not only terrains).

An LSD is a geometric embedding of the contour tree where each point of the contour tree is mapped to the isobarycenter of the corresponding level set contour.

In [START_REF] Lazarus | Courbes, cylindres et métamorphoses pour l'image de synthèse[END_REF], we used the shortest path distance to a source point to define a function on the vertices of a polyhedron. The same function is used by Axen and Edelsbrunner [START_REF] Axen | Auditory morse analysis of triangulated manifolds[END_REF] in a very different context. In this work, the topology of surfaces is explored by a wave traversal to produce sounds in relation with the topology of the surface. The waves precisely correspond to level sets of the shortest path distance to a source point. Note, however, that Axen and Edelsbrunner consider topological distances -edges have unit length -rather than Euclidean distances. Section 2 presents some basic definitions and properties of the level sets of a function defined on a triangulated polyhedron. In Section 3, we describe the evolution of a the level-sets as the level is varied. This description is based upon the notion of index of a vertex. Section 4 studies the level sets of the shortest path distance to a source point. This study is used in Section 5 to define efficient algorithms that construct the LSD. Results are commented in Section 6. Finally, we discuss future works and conclude in Section 7.

Level Sets of Functions

This section provides some definitions and notation that are important to the construction and properties of the LSD. In the following, we only consider LSDs of triangulated polyhedra.

For a given triangulated polyhedron, P, we consider a function, f , defined over its vertices v1; : : : ; vn so that two adjacent vertices are given two different values. Actually, as noticed in [START_REF] Takahashi | Algorithms for extracting correct critical points and constructing topological graphs from discrete geographical elevation data[END_REF], all that is required is to tell which of any two adjacent vertices gets the smaller value. In practice, we can order arbitrarily the vertices having the same value so that the above requirement can be alleviated.

Definition 1 An edge (vi; vj ) is said to be a cross-edge relatively to a level l if f (vi) < l < f (vj):

Similarly, a face (vi; vj ; v k ) is said to be a cross-face relatively to a level l if the three values of its vertices encompass l, that is

f (vi) < l < f (vj) < f (v k ); or f (vi) < f (vj) < l < f (v k ):
Remark that a cross-face has exactly two cross-edges.

Definition 2

The dual graph of P is the graph whose vertices are the faces of P and whose edges correspond to pairs of incident faces.

The preceding remark shows that a cross-face (relatively to a level l) is adjacent to exactly two cross-faces in the dual graph (see Figure 2). Vertices with values greater (smaller) than l are marked with a "+" (a "-").

Property 1 For any level l, distinct from the values f (v1); : : : ; f (vn), the set of cross-faces constitutes a set of disjoint cycles in the dual graph.

This property is to be compared with the fact that a level set of a Morse function defined on a closed smooth surface is composed of disjoint closed curves, if that level set contains no critical point.

These cycles of cross-faces define closed polygonal contours on the polyhedron P. For this, we associate with each cross-edge

(vi; vj ) the point pij (l) = l f (vi) f (vj) f (vi) vi + f (vj) l f (vj) f (vi) vj : If (vi; vj ; v k
) is a cross-face, we can draw the line pij (l)p ik (l) as on Figure 3.

Definition 3

The geometric realization of a level set is the set of polygonal contours obtained by drawing the lines (pij(l)p ik (l)) in every cross-faces. We will note C(l) the realization of the level set of level l. (l) p ik (l)

v i v k v j p ij
Figure 3: Segment (pij(l)p ik (l)) is the geometric realization of the cross-face (vi; vj ; v k ).

These polygonal contours are not necessarily planar. They will be further "averaged" in order to construct the LSD.

If l1 < l2 are two levels, such that no vertex v verifies l1 f (v) l2, then the two corresponding level sets are traversed by the same cross-faces. It follows that C(l1) can be deformed continuously into C(l2) and vice versa. In other words, C(l1) and C(l2) are homotopic. In particular, they have the same number of contours. This result will be strengthen in the next section. As we will see, the contours are still homotopic when the level l passes through a value f (v), as long as v is a regular vertex.

Vertex Index and Euler Formula

The LSD encodes the set of contours C(l) as l evolves. Branching of the LSD can only occur when C(l) changes of homotopy type. It is thus important to know for which value of l the topology of the polygonal contours C(l) is modified. As we just saw, this can only happen when l equals f (v) for some vertex v of the polyhedron P.

In order to describe the topological change at a vertex v we introduce the index of a vertex v. Let w1; w2; : : : ; w k be the k neighbors of v enumerated counterclockwise around v.

As Takahashi et al. [START_REF] Takahashi | Algorithms for extracting correct critical points and constructing topological graphs from discrete geographical elevation data[END_REF], we consider the number of sign changes, Sgc f (v), in the sequence (f(w1) f (v); f (w2) f (v); : : : ; f (w k ) f (v); f (w1) f (v)). The index of v is defined as 4 shows a vertex with index 1. proof: Sgc f (v) counts the number of triangles (vi; v; vj ) incident to v such that f (v) is between f (vi) and f (vj). Since every triangle has exactly one vertex for which this occurs the sum of the Sgc f (v) for all the vertices counts the total number of triangles:

Ind f (v) = 1 Sgc f (v) 2 Figure
X v2P Sgc f (v) = nF ; so that X v2P Ind f (v) = nV 1 2 nF :
As P is a triangulation, we have 3nF = 2nE or equivalently nF = 2(nE nF ). It follows that

X v2P

Ind f (v) = nV nE + nF = (P) 2

The same formula can be found in [START_REF] Banchoff | Critical points and curvature for embedded polyhedral surfaces[END_REF] and [START_REF] Henle | A Combinatorial Introduction to Topology[END_REF] in a slightly different context. Takahashi et al. [START_REF] Takahashi | Algorithms for extracting correct critical points and constructing topological graphs from discrete geographical elevation data[END_REF] implicitly refer to a similar formula but they only consider vertices for which Sgc f (v) equals 0 or 4. In fact, Takahashi et al. directly refer to Morse theory. In this theory a critical point may only get three different index values, two of which corresponding to local extrema. Another effective analogy is provided with the notion of index of a critical point of a gradient vector field. A critical point of a vector field is a (isolated) point where the vector field is null. Very roughly speaking the index of a critical point is the number of revolutions made by the vector field while turning around that point [START_REF] Henle | A Combinatorial Introduction to Topology[END_REF]. In order to show the analogy with our notion of index, we first orient the edges according to the fvalues of their endpoints. This orientation corresponds to the gradient of f along the edges. Note that a triangle cannot have its edges oriented clockwise nor counterclockwise as shown in Figure 5. Then, in each triangle of P we draw a continuous vector field, as sketched on Figure 5, so that the direction of the vector field on the triangle boundary agrees with the orientation of its edges. Now, the vertices of P are the critical points of this vector field and it can be shown that their index, relatively to the vector field, coincides with our notion of index. The above Euler formula thus corresponds to a classical summation formula over the index of the critical points of a continuous vector field [START_REF] Henle | A Combinatorial Introduction to Topology[END_REF].

The index of a vertex v describes how the level set realization

C(l) is modified around v, as the level l is raised from f (v) to f (v) + , for a sufficiently small . v k v i v i v j v j v k
(f (vi) < f (vj) < f (v k )).
On the right: The tangent vectors to the oriented curves defines a vector field compatible with the edge orientation.

If Ind f (v) is null, then the v neighbors are partitioned into two connected sets fv jf(v ) < f (v)g and fv+jf(v+) > f (v)g as shown in Figure 6 on the left. C(f(v) + ) is deduced v v - - - - - + + + + + + + Figure 6: The neighborhood of a vertex v in two different con- figurations. a '+' ('-') indicates a v neighbor, w, such that f (w) is greater (smaller) than f (v).
The level set realization is shown for a level slightly below f (v) (dotted curve) and slightly above f (v) (plain curve). The index of v is 0 on the left and -1 on the right.

from C(f(v) ) by substituting points on cross-edges of the type (v; v ) to points on cross-edges of the type (v; v+). The change reduces to a sweep and a chain substitution of cross-

edges so that C(f(v) + ) is still homotopic to C(f(v) ).
Several chain substitutions may occur at the same time when different non adjacent vertices get the same value f (v).

Definition 4 A vertex with a null index is said to be regular and critical otherwise. Similarly the value f (v) of a critical vertex is called a critical value. Any other value is said to be regular.

Note that a positive index (+1) indicates a local extremum. A critical vertex which is not an extremum is called a saddle vertex. When traversing a critical value the topology of the level set is changing. The evolution of the level set depends on the index of the corresponding critical vertex (see Figure 6). The precise topological change not only depends on the index but also on the whole configuration of the level set. from the vertex indices when considering the shortest path distance to a source point on a genus-0 polyhedron.

The Shortest Path Distance to a Source Point

Up to this point we have not considered any specific f . As we want the LSD to represent the object geometry, the definition of f should involve the geometry of P. Takahashi et al. use the height function [START_REF] Takahashi | Algorithms for extracting correct critical points and constructing topological graphs from discrete geographical elevation data[END_REF], so that any vertex is associated its own zcoordinate in a suitable coordinate system. In this case, the level sets correspond to cross-sections between P and xy-planes. As noticed in the introduction this choice is relevant for terrain data as the critical vertices correspond to peaks, passes or pits of the terrain. However, for other classes of objects it may happen that the height function does not give an intuitive LSD in any coordinate system. Figure 13 shows a self-intersecting tubular object whose "natural" axis could not be determined with any height function. A better choice for the level sets is provided with the moving front of some flow emanating from a tip of the tube. Such fronts correspond to the level sets of the geodesic distance to a tip of the tube. The computation of the geodesic distance to a source point on a polyhedron has been extensively studied (see [START_REF] Mitchell | The discrete geodesic problem[END_REF]). We prefer to compute the shortest path distance relatively to the graph induced by the edges of a polyhedron. It provides an approximation, sufficient for our purpose, of the geodesic distance. It further allows us to simplify and accelerate the computation and fits nicely into a theoretical framework.

In the following, we study the level sets of the shortest path distance to a given source point. We will note the function ds instead of f . For any vertex v, ds(v) is the length of a shortest path to a given source point s. (The choice of s will be discussed in the results section.) ds can be computed efficiently with a modified breadth-first search starting from the source and using the classical Dijkstra's algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF]. Dijkstra's algorithm makes use of a priority queue to select the next vertex to be processed in the breadth-first search. Dijkstra's algorithm also returns for any vertex v a pointer (v) to the preceding vertex on a shortest path linking v to the source s. By iterating the pointer we can follow a strictly decreasing path from any vertex to the source.

ds presents interesting properties that allows for easy computation of the associated LSD. First of all, the source point s is the only local minimum of ds. This means that from any vertex we can draw a path of edges leading to the source point with strictly decreasing vertex ds-values. To obtain further nice properties we will assume from now on that the polyhedron P has a 0-genus, that is P is topologically equivalent to a triangulated sphere.

With this assumption, we get the following property that will provide a complete description of the topological change when the level passes through a critical value.

Property 3

The set of cross-faces incident to v for a level l lower than ds(v) belong to a unique cycle.

proof: Since P has a 0-genus, the realization of any level set cycle splits P into two connected components. If such a cycle contains a cross-face incident to v, then one of these two components must contains v while the other contains the source point. This is easily seen from the above decreasing path property (see also Figure 8 Since p meets the whole level set C(l) exactly once, there must be only one such cycle 2

From this property it is seen that the configuration of Figure 7 on the right cannot occur. Also, if nc(l) counts the number of cycles of C(l), then for any vertex v, we have nc(ds(v) + ) = nc(ds(v) ) Ind ds (v) ; since any chain of v neighbors further than v from the source gives rise to a new cycle (see Figure 7 left).

Property 3 prevents the LSD from having loops. The vertex with the highest distance ds on a loop would indeed have two branches going down the source which would contradict property 3. Since the LSD is connected (just follow a decreasing path to the source from any vertex on a cycle), the LSD must be a tree.

The tree structure of the LSD is recorded into a contour tree [22] Ts(P) whose root, internal nodes and leaves are respectively the source s, the saddle vertices, and the local maxima.

The lines of Ts(P) link critical vertices and correspond to cylindrical parts of P. Figure 9 shows a simple example. In practice, we will use its tree structure to construct the LSD.

Algorithms

We present algorithms for computing the tree Ts(P) and the LSD associated with the distance ds. To clarify the presentation we assume that no two vertices of P are at the same distance from the source. In case this would happen, we can still arbitrarily order the vertices having the same distance so that we can compare any pair of adjacent vertices. In [START_REF] Axen | Auditory morse analysis of triangulated manifolds[END_REF], this kind of degeneracies is treated by first performing a barycentric subdivision. However, this technique does not apply here as we are not considering topological distances. Also, the barycentric subdivision does not solve all the degeneracies (i.e. adjacent critical vertices with the same distance) and further arbitrary choices must be taken.

We also assume that the neighbors of a vertex, the incident faces to an edge, and the edges and vertices of a face can be accessed in constant time O(1). The winged-edge data structure [START_REF] Baumgart | A polyhedron representation for computer vision[END_REF][START_REF] Weiler | Edge-based data structures for solid modeling in curved-surface environments[END_REF],

for instance, fulfills all these requirements.

To construct the LSD, we need to sweep the level from zero to its maximum value max ds and compute the "average" point of various level set cycles.

The set of cross-faces contained in a level set changes whenever the level passes trough a vertex value. The number of different level sets is thus equal to the number of vertices. Since most of the vertices have to be regular most of these level sets will have the same topology. Also, polyhedral objects may have hundreds or thousands of vertices, and we do not need that many level sets to construct the LSD. In practice, we fix the number of levels (from 16 to 50 in our examples) and select the levels uniformly in the range 0; max ds]. For each selected levels, we must compute the corresponding level set realization. This requires finding a starting cross-edge in each cycle of the level set. Then, from faces incident to these starting cross-edges, we can walk the dual graph of P along the level set and determine all the level set cycles.

These starting cross-edges play the role of what van Kreveld et al. [START_REF] Van Kreveld | Contour trees and small seed sets for isosurface traversal[END_REF] call a seed set. In our case there is no need to compute such a seed set. The tree structure Ts(P) of the LSD actually provides an efficient tool to determine a starting edge in each cycle of any level set. Precisely, we build the LSD while traversing the lines of Ts(P). For each line (si; sj ) of Ts(P)

we can obtain a starting cross-edge in any cycle contained in the associated cylindrical part. This is done with a decreasing path starting at sj as shown in Figure 10. As the construction algorithm is guided by the tree structure Ts(P), we can assure that we do not miss any cycle in a level set and that each cycle is computed only once.

The overall LSD construction algorithm is thus based on two steps: in a first step, we build the tree Ts(P), and in a second step, we compute the LSD itself.

Computing T s (P )

The construction of Ts(P) is based on Dijkstra's algorithm. It is performed while traversing the adjacency graph of P. During this traversal, we compute the shortest path distance ds of the visited vertices as well as the pointer to the preceding neighbor on a shortest path. As for the classical Dijkstra's algorithm, we maintain a priority queue with respect to the distance. This priority queue contains the vertices adjacent to the already visited vertices, but whose distance have not yet been fixed by the algorithm. Since in the Dijkstra's algorithm vertices are processed in their order of distance, this traversal amounts to sweep a level set from distance zero to the maximum distance.

The construction of Ts(P) is directly inspired from the contour tree algorithm in [START_REF] Van Kreveld | Contour trees and small seed sets for isosurface traversal[END_REF]. Starting from the root, we visit the vertices of P until we encounter a singular vertex v. At this point, we create a line (s; v) of Ts(P). If v is a local maximum the construction is stopped and Ts(P) reduces to the single line (s; v). Otherwise, v must be a saddle vertex, and we split the priority queue into 1 Ind ds (v) subqueues corresponding to the branches of Ts(P). In order to represent several branches (i.e. subqueues) in the priority queue, we label every vertex v in the queue with a contour number c(v). Splitting a contour in the queue amounts to replace the contour number of its vertices by traversing each new contour. We also maintain a contour table CT containing for every contour i the saddle vertex CT i] that gave birth to this contour branch during the sweep.

The algorithm proceeds as follows 0 (Initialize) Q : a priority queue of vertices w.r.t. ds for each vertex v of P Mark v as unprocessed.

ds(s) = 0 (s) = N U LL Q = fsg
Insert s as the root of Ts(P)

CT 1] = s nc = 1 (nc is the number of contours in the queue)

c(v) = 1 1 (Main loop) begin 1 while Q is not empty do begin Extract v = head of Q and dequeue Q Mark v as processed 5 for v i adjacent to v and marked unprocessed do if v i is not in Q then begin Set ds(v i ) to ds(v) + kv v i k Set (v i ) to v 10 Set c(v i ) to c(v) Insert v i into Q end else if ds(v i ) > ds(v) + kv v i k then begin 15 Change ds(v i ) to ds(v) + kv v i k Change (v i ) to v Change c(v i ) to c(v) end Compute the index Ind(v) 20 if Ind(v) = 1 (v is a local maximum) then
Insert line (CT c(v)]; v) into Ts(P) with v as a leaf else if Ind(v) < 0 (v is a saddle point) then begin

Insert line (CT c(v)]; v) into Ts(P)

25 Split contour c(v) into 1 Ind(v) subcontours corresponding to the cycles incident to v of the level set C(ds(v) + )
Use the old contour number c(v) and the new numbers nc + 1; : : : nc Ind(v) for the new contours 30

CT c(v)] = v for 1 j Ind(v) do CT nc + j] = v nc = nc Ind(v)
end end end Analysis In the following we sketch some proof for correctness of the algorithm and analyze its complexity.

Statement 1 Ind(v) can be correctly computed at line 18 of the main loop.

In the classical Dijkstra's algorithm vertices are dequeued in distance order [START_REF] Cormen | Introduction to Algorithms[END_REF]. This is still true in our case as we use Dijkstra's algorithm without changing the order of processing of the vertices.

When dequeuing a vertex v (line 3), all the adjacent vertices with a distance smaller than ds(v) have already been processed while all the other adjacent vertices must lie in the queue with their distance set to a value greater than ds(v). It follows that Ind(v) can be correctly computed.

Statement 2 When Q is dequeued (line 3 of the main loop), it contains the extremity of all the cross-edges, relatively to the level ds (v) , and these extremities are labelled according to the connected components, or contours, of the level set ds (v) .

When Q is dequeued in line 3, the origin of every cross-edge, relatively to the level ds (v) , obviously lies at a distance smaller than ds(v) from the source. According to the order of processing, all these origins must have been processed earlier.

It follows that the extremity of these cross-edges have been enqueued at line 11 ( is chosen so that no vertex other than v has its distance in the interval ds (v) ; ds(v)]).

Until the first saddle vertex is processed, all the vertices in Q have the same label, 1, and we know that the current level set is composed of a single contour.

When a local maximum is encountered, the corresponding contour simply disappears from the queue. When a saddle vertex w is encountered, the corresponding contour c(w) can only split into 1 Ind(w) contours, according to Section 4. Lines 24-31 of the main loop precisely performs this split.

To do so, we walk along each cycle of C(ds(w) + ) corresponding to a chain of +'s (see Figure 7 Right) and change the label c() of the extremity of the traversed cross-edges.

By construction, Q contains: either the vertices which had a label different from c(w) just before w is dequeued, or the upper extremities of all the cross-edges relatively to the 1 Ind(w) contours of level ds(w) + and these extremities have been labelled according to their corresponding contours.

Then Q is further dequeued and the statement follows by induction on the number of singular vertices.

Statement 3 The main loop correctly computes the tree Ts(P).

From statement 2 it is seen that each iteration of the main loop corresponds to the sweep of all the level set cycles with respect to the distance ds and it maintains the labelling of the vertices according to the level set cycles already encountered.

When a singular vertex w is dequeued, the branch containing the contour c(w) (more precisely, the contour just below c(w)) either splits or terminates. At this point, we must create a line in Ts(P). This line must have w as its extremity and the saddle vertex that gave birth to this branch as its origin. By construction this origin is precisely CT c(w)] and the branch is correctly taken into account at line 21 or 24 of the main loop. From Dijkstra's algorithm all the vertices of P must be processed so that the main loop visits the entire tree.

The complexity of the algorithm reduces to the complexity of the Dijkstra's algorithm plus the time for splitting the queue. Using a Fibonacci heap for the priority queue, Dijkstra's algorithm requires time O(n log n) for a polyhedron with n vertices 2 . A contour c(v) must be split each time a saddle vertex is met. The total time spent for splitting the queue is thus bounded by ns max, where ns counts the number of saddle vertices and max is the largest number of cross-edges in a contour. Hence, the computation of Ts(P) requires time O(n log n +ns max). ns and max can be as large as O(n) so that this analysis may lead to an O(n 2 ) complexity in the worst case. When all splits are simple (i.e. the contour c(v) can only split into two parts c1 and c2), van Kreveld et al. [START_REF] Van Kreveld | Contour trees and small seed sets for isosurface traversal[END_REF] propose to reduce the cost for splitting by traversing the smaller of c1 and c2 rather than traversing both of them. This is done by tandem search, that is by traversing the two contours c1 and c2 in parallel until one contour, say c1, is entirely traversed. Then, c1 is traversed again and the label of its vertices are changed accordingly. This way, the cost for splitting c(v) is proportional to the size of c1 (the smaller of c1 and c2). This leads to an O(n log n) time algorithm to compute the contour tree Ts(P) (see [START_REF] Van Kreveld | Contour trees and small seed sets for isosurface traversal[END_REF] for a proof).

The same complexity can be obtained for non simple splits by extracting all but the largest contour from the contour c(v) at a branching node.

Computing the LSD

The LSD constitutes a geometric embedding of Ts(P). In practice, we discretize the level interval 0; max ds] into a set fl1; l2; : : : ; lrg of r levels and compute the average point of each cycle of the level set realizations C(l1); : : : ; C(lr). The algorithm proceeds by traversing the tree Ts(P). For each line of the tree we compute and average the cycles of level l1; : : : ; lr contained in the corresponding cylindrical part.

(Main loop) begin 1 for each line ( ; 0 ) of Ts(P) do begin x = 0 for each level l i with ds( ) < l i ds( 0 ) 5 taken in decreasing order do 2 Dijkstra's algorithm works with any connected graph in time O(n log n + p) if p is the number of edges.

(c i ; x) = processCycle(l i ; x) Create a skeletal curve interpolating the points c i This formula is independent of the discretization level and avoids the artifacts caused by non-uniform meshes.

Remark that in line 4 of the main loop we replaced the inequalities ds( ) < li < ds( 0 ) involved in the definition of a crossedge by the inequalities ds( ) < li ds( 0 ). This avoids precision problems when li equals ds(v) for some vertex v. In such a case, the topology of the level set will be the same as the topology of C(li ), though the embedding might have a singular point at vertex v.

In line 7 of the main loop we can use a simple polygonal curve or a curve fitting algorithm [START_REF] Schneider | An algorithm for automatically fitting digitized curves[END_REF][START_REF] Eilers | Smoothing and interpolation with finite differences[END_REF]. Note that our algorithm provides a curve for each branch of the LSD but does not tell how the branches are geometrically linked together. The problem is that the barycenter becomes discontinuous each time a cycle is split into several cycles. In other words, the position of the barycenter of every new cycle changes abruptly from the position of its "parent" cycle. This branching information is yet important for animation and deformation purposes. Therefore, we keep virtual links between the branches according to the tree structure. In the Figures of the results Section branching links are visualized with line segments.

Results

We present and discuss the results of applying our LSD algorithm to a number of polyhedral objects.

Source point location.

In our current implementation the source point can be selected either automatically or interactively. In the former case we apply a heuristic based on a simple Figure 11: A swan and its LSD. The swan is composed of 1728 faces. 20 level lines have been built from 5% to 90% of the maximal distance from the source point which is located at the extremity of its beak (indicated by a white triangle on figure 12). The LSD was obtained in less than a second on a SGI INDIGO2.

algorithm to find a diameter of a tree. A diameter of a tree is a pair of vertices separated by the largest possible distance in the tree. Intuitively, the two vertices of a diameter are located at the tip of a longest branch of the tree. The following procedure determines a tree diameter:

1. Pick a vertex x at random in the tree, 2. Find y such that dx(y) is maximal, 3. Find z such that dy(z) is maximal.

It is relatively easy to show that (y; z) is a diameter. In our case we keep the two first steps of the procedure to find a source point s (= y) which corresponds to the tip of some long branch of our polyhedral object. The source point was selected automatically on Figures 11,[START_REF] Milnor | Morse theory[END_REF][START_REF] Mitchell | The discrete geodesic problem[END_REF] The shortest path distance is continuous with respect to the source point since jds(x) d s 0 (x)j ds(s 0 ) = d(s; s 0 ):

As a consequence, the LSD is stable with respect to the source point location, as illustrated in Figure 12. Note that the 0-level set coincides with the source point. In order to avoid small deviations due to the precise location of the source point we only draw part of the LSD. We actually remove a small percentage of the LSD at each of its extremities. On Figure 13, on the right, we can see the artifact caused by the selection of the source point on the border of the bottom knot section (the two endsections are triangulated without any interior point).

Self intersecting objects. Figure 13 shows that our LSD algorithm can handle self-intersecting objects. This would not be the case if we had chosen a height function instead of the shortest path distance. The Medial Axis transform would also fail Extension to non triangulated objects. Notice that the swan and the knot on Figures 11 and13 are not triangulated. In [START_REF] Lazarus | Courbes, cylindres et métamorphoses pour l'image de synthèse[END_REF] an extension for extracting LSDs of non triangular meshes is proposed. In a first step we add virtual edges to the polyhedron graph so that the restriction of the new graph to any face is a complete graph. The shortest path distance is computed with this new graph. The definition of a cross edge is also modified to take into account the fact that a face may have more than two cross-edges (see [START_REF] Lazarus | Courbes, cylindres et métamorphoses pour l'image de synthèse[END_REF] for more details).

The LSDs of the man, the dolphin and the horse3 of Figures 14, 15 for any kind of shape. If the object has no obvious tree structure, as for the case of a spherical object, the LSD algorithm still produces a one dimensional structure. Depending on the application this may or may not be useful.

Note that the LSD may lie outside the object. Consider a punched sphere, forming a bowl, with the source point on its bottom (see Figure 17, left). The level sets are circles propagating from the source point up to the rim of the bowl and further shrinking down to the bottom on the interior surface of the bowl. The LSD of this bowl is composed of a straight line going outside the bowl interior up to the rim level, and turning back to the bottom. Although this might not correspond to the intuitive idea of a skeleton this LSD can be used for deforming the bowl (see Figure 17) with an axial deformation tool [START_REF] Lazarus | Axial deformations: an intuitive deformation technique[END_REF]. Generally speaking, the LSD provides a set of tubular parameterizations together with articulations that can be used for animation systems. For instance, Walter and Fournier's animation System [START_REF] Walter | Growing and animating polygonal models of animals[END_REF] could certainly take advantage of the LSD.

Finding axial structures is also helpful for extraction of surfaces from scattered point sets (see [START_REF] Shinagawa | Constructing a Reeb graph automatically from cross sections[END_REF]). In [START_REF] Verroust | Extracting skeletal curves from 3D scattered data[END_REF] we propose an algorithm, based on the level set paradigm, for extracting skeletal curves from 3D scattered data. It is especially relevant for medical data such as blood vessels.

As presented here, our algorithm in Section 5.1 only applies to 0-genus surface. Following van Kreveld et al. [START_REF] Van Kreveld | Contour trees and small seed sets for isosurface traversal[END_REF], this could easily be extended to construct LSDs of non-0 genus surfaces. Some minor modifications are to be made in order to get a starting cross-edge in each contour of a level set. In the case of a 0 genus surface, the level set just below a saddle vertex is composed of a unique contour (contours can only split). It follows that a single decreasing path from a saddle vertex is sufficient to get a starting cross-edge for any contour below a saddle vertex. In Section 5 this decreasing path is provided by the pointer. In the case of a non-0 genus surface, however, contours can also merge at a saddle vertex. We thus need to obtain starting crossedges in every branch below such a saddle vertex. This can be done by considering as many decreasing paths as there are sequences of "-" in the cycle of neighbors of the saddle vertex (see Figure 7 on the left).

Finally, when applied to scattered point sets, coupling our technique with the feature-based surface generation developed by Takahashi et al. [START_REF] Takahashi | A feature-based approach for smooth surfaces[END_REF] would provide an efficient reconstruction tool.

Figure 2 :

 2 Figure2: A triangulation with its cross-adjacency graph (bold lines) for a given level l. Vertices with values greater (smaller) than l are marked with a "+" (a "-").

Figure 5 :

 5 Figure 5: On the left: Orientation of the edges of a triangle induced by f (f (vi) < f (vj) < f (v k )). On the right: The tan-

Figure 7 :

 7 figuration of C(f(v) ). As will be shown in the next section the topological changes of the level sets can be deduced directly

Figure 8 :

 8 Figure 8: The path p : v ! s meets the realization of any level set cycle containing one or more cross-faces (shaded on the Figure) incident to v once and only once.

5 Figure 9 :

 59 Figure9: The LSD is an embedding of the tree Ts(P). On the left the LSD is computed from five level sets of ds corresponding to the distances d1; : : : ; d5.

Figure 10 :

 10 Figure 10: The pointer provided by the Dijkstra's algorithm is used to find a starting cross-edge (y; z) of a cycle contained in the cylindrical region between s1 and s3.

end

  Figure 10 summarizes the construction of a cycle in processCycle. In line 10 of processCycle we compute the barycenter of the polygonal curve C rather than the barycenter of its vertices. If C = (p1; p2; : : : ; p k ) then c = k X j=1 kpjpj+1k pj + pj+1 2 =

Figure 12 :

 12 Figure 12: Left: the white and black arrows designate the two source points used to compute the LSDs. Right: the two corresponding LSDs are almost identical.

Figure 13 :

 13 Figure 13: Left: front view of a self intersecting knot and its LSD. Middle: lateral shaded view of the knot. Left: the LSD seen from the same viewpoint.

  and 16 have branches. 16 level have been used for the horse, 31 for the dolphin and 50 for the man.

Figure 14 :

 14 Figure 14: The man (left) is composed of 14946 faces. The source point was selected on the top of the man's head. The LSD (middle) was computed in 7.74 seconds on a SGI Indigo. Details of the LSD is shown on the right.

Figure 15 :

 15 Figure 15: The dolphin is composed of 563 faces and the LSD was computed in 0.25 seconds on a SGI Indigo.

Figure 16 :

 16 Figure 16: A horse and its LSD. The horse is composed of 22258 faces and the computation of the LSD lasted 5.41 seconds on a SGI Indigo.

Figure 17 :

 17 Figure 17: Left: the bowl and its corresponding LSD. Right: the deformed bowl after bending the LSD.

  which does not necessarily produces a one Université de Poitiers. I.R.C.O.M.-S.I.C. SP2MI, Boulevard 3, Teleport 2, B.P. 179, 86960 Futuroscope Cedex, FRANCE y INRIA Rocquencourt, Domaine de Voluceau, B.P. 105, 78153 Le

	Chesnay Cedex, FRANCE

This index tells how f

  (P) = nV nE + nF is the Euler characteristic of P and nV , nE and nF are respectively the number of vertices, edges and faces of P.

			is changing around v. It actually records part of the topology of P itself. By summing the indices over all the vertices, we get
			the very nice formula
			Property 2	X v2P	Ind f (v) = (P)
	-	+
	+	v	+
	-	-
	Figure 4: A "+" (a "-") indicates a v neighbor, w, such that f (w) is greater (smaller) than f (v). The number of sign changes Sgc f (v) counts the number of "+" and "-" sequences.

where

A Morse function, on a surface, is a twice differentiable function whose Hessian -the Jacobian of the gradient in a suitable coordinate system -has a non-zero determinant everywhere its gradient vanishes.

Copyright 1988, Rhythm & Hues Studios, Inc.

Discussions and Future Work

We have described an efficient algorithm for constructing the LSD associated to a genus-0 polyhedron whose vertices are valued by the shortest path distance to a source point. This algorithm is fast, robust, and easy to implement. It is mainly designed for tubular and branching objects although it works

Acnowledgements

The authors would like to thank the anonymous reviewers for their valuable comments and for providing useful references ([2, 7, 22]).