Bingqing Qu

Félicien Vallet
email: fvallet@ina.fr

Jean Carrive
email: jcarrive@ina.fr

Guillaume Gravier
email: guillaume.gravier@irisa.fr

Using Grammar Induction to Discover the Structure of Recurrent TV Programs

Keywords: TV program structuring, symbolic representation, structural grammar induction, unsupervised approach

Video structuring, in particular applied to TV programs which have strong editing structures, mostly relies on supervised approaches either to retrieve a known structure for which a model has been obtained or to detect key elements from which a known structure is inferred. In this paper, we propose an unsupervised approach to recurrent TV program structuring, exploiting the repetitiveness of key structural elements across episodes of the same show. We cast the problem of structure discovery as a grammatical inference problem and show that a suited symbolic representation can be obtained by filtering generic events based on their reoccurring property. The method follows three steps: i) generic event detection, ii) selection of events relevant to the structure and iii) grammatical inference from a symbolic representation. Experimental evaluation is performed on three types of shows, viz., game shows, news and magazines, demonstrating that grammatical inference can be used to discover the structure of recurrent programs with very limited supervision.

I. INTRODUCTION

Large scale audiovisual archives offer an extremely abundant digital TV program library for users and content providers. For instance, the French National Audiovisual Institute, a repository of French radio and television audiovisual archives, has more than five million hours of radio and television programs stored. However, in order to be useful for later usage such as Internet diffusion, browsing and sharing, such large-scale archives need to be appropriately indexed. In particular, structuring programs, i.e., obtaining a temporal segmentation of programs into their basic constituents, is a crucial step for high-quality indexing, enabling better description as well as direct access to meaningful excerpts.

TV program structuring consists in automatically recovering the structure of a program from the video material, where structure refers to the way in which a program is organized by editors. In the video, the underlying program structure is often reflected in editing rules. Also, the structure of a program is consistent across the different episodes. For example, TV news programs usually start with a brief outline of the reports announced by the anchorperson. Headlines are followed by an alternation of anchorperson's announcement of the upcoming topic and news reports. Most news programs end with interview segments, weather forecasts or program trailers.

Program structuring aims at detecting the existence and the temporal boundaries, i.e., the start and end frames, of such constituting elements designated as the structural elements, or events, of the program. In the framework of recurrent programs, i.e., of programs for which several episodes are available, a structural element refers to a video segment with a particular syntactic meaning and which can be regularly found in different episodes.

In this paper, we report ongoing work investigating grammatical inference to discover the basic structural elements as well as their temporal ordering, i.e., the temporal structure, by analyzing a collection of episodes from the program with minimal prior knowledge about the program genre and about the type of structural elements which might be present. In particular, we make very limited assumptions on what structural elements should be, as opposed to supervised approaches which seek to retrieve structural elements previously deemed as relevant for a type of program. To skirt the issue of not knowing which structural elements to look for, we exploit the repetitive nature of recurrent TV programs. A recurrent TV program is a program with multiple episodes which are periodically broadcasted, e.g., daily, weekly. News, entertainments, games and magazines are typical recurrent programs. Most episodes, if not all, follow the same editorial structure: structural elements appear in almost the same order with very similar durations, separated by sequences which repeat across episodes at more or less the same time instants. This last property is successfully used in [START_REF] Abduraman | An unsupervised approach for recurrent tv program structuring[END_REF] to detect separators. We adopt a similar idea, further exploiting separators to yield a symbolic representation of episodes suited for grammatical inference. By searching for recurrent elements throughout the episodes and selecting the ones which are relevant to the structure, one can infer the grammar of the show, i.e., the time ordered sequence of structural elements that each episode follows. Assuming such a grammar can be found, a model of the structure of the show can then be established to process additional episodes.

As a proof of concept, we focus here on grammar inference, implementing a three steps approach based on the sole visual modality. Firstly, a batch of broad scope event detection tools are used to find various types of events in all episodes. Secondly, events detected are analyzed across episodes to select the ones relevant to the structure of the program. Finally, a symbolic representation is derived from the segmentation given by structural element s and grammatical inference is applied to yield a grammar of the program by analyzing the symbolic time-ordered representation of each episode.

The rest of the paper is organized as follows. Section II reviews the existing techniques for TV program structuring. Section III explains the overall method and details each step towards grammar induction for unsupervised TV program structuring. Experimental evaluations are reported in Section IV, followed by conclusions and perspectives in Section V.

II. RELATED WORK

TV program structuring has been extensively studied, almost exclusively relying on supervised approaches, which can be classified in two categories, depending on whether a particular program is targeted or not.

Previous work on TV program structuring mainly focused on the case where information on the structure is available as prior knowledge, thus enabling the use of supervised classification techniques. This is typically the case when targeting news or sports, two domains which have received tremendous attention (see, e.g., [START_REF] Zhang | Automatic parsing of news video[END_REF], [START_REF] Bertini | Content-based indexing and retrieval of tv news[END_REF], [START_REF] Li | Automatic detection and analysis of player action in moving background sports video sequences[END_REF], [START_REF] Duan | A unified framework for semantic shot classification in sports video[END_REF]). Assuming the entire structure of the program is relevant, models of the structure can be learned from annotated data. Hidden Markov models, in multiple variants, have been widely used to this end [START_REF] Xie | Structure analysis of soccer video with domain knowledge and hidden markov models[END_REF], [START_REF] Kijak | Audiovisual integration for tennis broadcast structuring[END_REF]. Event detection has also been used as an alternative to structure modeling. In this case, models are designed for the events of interest, e.g., goal or penalty in soccer, violent scenes in movies, and parameters are estimated on annotated training data.

Resorting to prior knowledge on the structure offers relatively accurate structuring algorithms but is limited by nature to specific types of programs, requiring training data for each new type. As an alternative, research has targeted the detection of typical structural elements, i.e., of events related to the structure independently of the different program types. Such elements are very diverse, such as anchorperson [START_REF] Hanjalic | Template-based detection of anchorperson shots in news programs[END_REF], [START_REF] Gao | Unsupervised video-shot segmentation and model-free anchorperson detection for news video story parsing[END_REF], typical scenes or separators [START_REF] Abduraman | An unsupervised approach for recurrent tv program structuring[END_REF], [START_REF] Abduraman | Audio/visual recurrences and decision trees for unsupervised tv program structuring[END_REF] as defined by their repetitiveness. Separators, which are short sequences separating the different parts of a program, are of particular interest to unsupervised structuring. However, program-independent structural elements are insufficient to yield a complete program structure.

Work reported in this paper attempts to make the best of both worlds, i.e., being independent of the program type and obtaining a complete model of the structure.

III. STRUCTURE DISCOVERY WITH GRAMMATICAL

INFERENCE

The global objective we are targeting consists in inducing a structural grammar for a recurrent TV program, taking advantage of the existence of a collection of episodes of the same program. To avoid any confusion, the term program refers to the name of the show, thus being disconnected from video material, while episode refers to an exemplar of the program. A structural grammar is comprised of the set of structural elements, representing the different elements which compose each episode, and their temporal order. For example, report and anchorperson's announcement are structural elements for a news program, on top of which a temporal model with occurrence probabilities can be built to form a structural grammar.

A natural idea to discover the temporal model is to use grammatical inference on a symbolic representation of the video material representing each episode. The main difficulty therefore lies in obtaining a symbolic representation of the episodes in the absence of prior knowledge on what structural elements are to be considered. To solve this problem, we take advantage of the redundancy of information across all episodes to obtain symbols in an almost unsupervised manner. Redundancy appears in the structural elements, as well as in the so-called separators which recurrently occur between structural elements. The key idea of our method is therefore to analyze recurrent separators to in turn find recurrent elements which are deemed structural elements and which can be used for grammatical inference.

Targeting this general idea, we propose a three steps approach as illustrated in Figure 1. In the first step, a set of broad scope event detectors are used to find events within each episode, which might be of interest as a potential structural element or as a potential separator. In the second step, we assess the set of events detected along two lines. Density estimation is used to assess repeatability, i.e., to find events which recurrently occur at about the same instant in each episode. Role recognition is further used to assign properties to structural elements so as to help in deriving a symbolic representation. Finally, we induce the structural grammar of the program by leveraging multiple sequence alignment techniques.

One of the benefits of this approach is the very limited supervision that is required, thus making it possible to virtually apply the method on any collection quite straightforwardly. In particular, no data annotation is required at any step of the process. Apart from the selection of episodes, minimal prior knowledge on the program genre is required to select relevant event detectors in the first step and, in the second step, to deduct a meaningful symbolic representation from the set of structural elements found.

We detail in turn each of the three steps.

A. Detection of broad scope events

Ideally, a large number of event detectors should be used, which are generic enough to apply to a large number of shows. This is however not very practical because of implementation and run time issues. A number of key event detectors must therefore be selected based on a trade-off between the type of programs to process, the complexity at run time and, to a lesser extent, the implementation complexity. In this work, five event detectors were used as described below. Note that only minimal knowledge on the type of programs to process was considered, resulting in general purpose detectors, which were applied to all types of programs in evaluation.

Shot detector. Shots are basic units for program structure which are required for structuring purposes. Shot boundaries were detected using the implementation of J. Mathe et al. [11] which seeks for hard cuts.

Dissolve detector. Gradual transitions are also common in TV programs, which usually signal the start and end of a scene. We focused on dissolve transitions, the most common gradual transition. Dissolve were detected using an extension of [START_REF] Mittal | Robust identification of gradual shot-transition types[END_REF] in which the dissolve feature description was improved using double chromatic difference.

Monochrome image detector. Monochrome images-mostly white or black-are usually added to the TV streams at edition time to separate the different parts of a program. Detecting monochrome images is therefore an obvious choice for structure discovery in TV programs, in particular due to the simplicity of implementation. In this work, monochrome images are detected by simply verifying the histogram variance of the images.

Person clustering. Persons are essential features for almost any type of TV program. Especially, in many programs, a few number of key persons appear and are strong structure cues, such as the anchorperson in news shows or the host in game shows. TV show conductors usually appear as the most dominant face in a program, i.e., the one which appears most. Dominant person is usually implemented using person clustering based on faces and clothing. Taking news as an example, the anchorpersons clothes are usually carefully chosen so as to be easily distinguishable from guests (and one from another in case of multiple anchors) and obviously do not change within an episode. Person clustering was implemented using Viola and Jones face detection [START_REF] Viola | Robust real-time object detection[END_REF] and dress bounding box determination [START_REF] Jaffré | Costume: A new feature for automatic video content indexing[END_REF]. A key frame of each shot with a face is firstly otained. For each key frame, face features [START_REF] Sivic | who are you?-learning person specific classifiers from video[END_REF] and clothing histograms are then used in a two-step clustering algorithm, shown in Figure 2, based on K-means and hierarchical clustering to obtain person clusters.

Shot reverse shot detector. Shot reverse shot is a classical video technique depicting shots alternating between two characters facing one another, usually engaged in some face to face interaction. In the case of TV programs, we assume that a segment of shot reverse shot represents a dialog and that such interaction between two characters are relevant to the structure. Based on the results of person clustering, we detect shot reverse shot segments by a straightforward analysis of the cluster interlacing.

B. Determination of structural elements

Events detected in the first step are obviously not all relevant to the structure of a program and cannot be used as is to obtain a symbolic representation of episodes. For instance, monochrome images appear between two parts of a game show as a separator, i.e., a structural element, but can also be found at other places such as in a night scene. The second step therefore consists in selecting valid structural elements from which the symbolic representation is obtained. Selection of structural events implements two complementary strategies. On the one hand, role recognition is used to further Role recognition. Role recognition enables determining the role of each person cluster resulting from face and clothing clustering. We mostly focus here on the conductor, or anchor, role which is clearly a strong cue with respect to structure. The first characteristic of the anchor is that he/she appears frequently, at more or less regular intervals and at key places, e.g., start and end of the each episode.

We used similar features as those defined in [START_REF] Jayagopi | Predicting two facets of social verticality in meetings from five-minute time slices and nonverbal cues[END_REF] to characterize a cluster, viz.: total duration of appearance (TFL); total number of distinct appearances, i.e., number of non consecutive clusters (TFT); duration of the longest segment in which the person appears (LFL); time range between the first and last occurrence (FR); duration in which the speaker is engaged in a dialog (DPT). Given such features, a dominant person is assumed to ideally have the following properties: he/she is the one that appears most (highest TFL); he/she is filmed the most frequently (highest TFT); he/she participates the most frequently in dialogs (highest DPT); his/her range of appearance (FR) and longest time of appearance (LFL) should not be the lowest. To account for varying episodes and programs lengths, all five features are scaled in [0, 1]. Decision on the dominant person is taken based on the sum of the five normalized features, the cluster for which the sum is maximal being identified as the dominant person.

Density filtering. In addition to role recognition, we exploit the property of repeatability across episodes to filter out events which occasionally appear in some episodes and which are therefore not relevant for the global structure of the program. Since different episodes of a recurrent program share a common temporal structure and have almost identical structural elements, the latter should appear in the vast majority of episodes and at about the same time.

Identifying elements which appear frequently at roughly the same time in all episodes is performed using temporal density analysis with a kernel function. For each type of event, we project onto the temporal axis the occurrences across all episodes of the event considered, counting the number of occurrences. To smooth out limited time variations, a kernel density estimation is used based on the following function where f (x; h) is the estimated density function, h the bandwidth and K() is the kernel. A Gaussian kernel was used with optimal bandwidth automatically chosen [START_REF] Botev | Kernel density estimation via diffusion[END_REF]. Peaks in the density estimation identify segments with high structural power due to their repetitiveness across episodes. Structural elements are selected based on thresholding of the density function to retain only relevant separators. This process is illustrated in Figure 3, where events in black are removed while the ones in gray are retained because of their high temporal concentration

f (x; h) = 1 nh d n i=1 K( x -x i h ) , (1)

C. Structural Grammar Induction

As a result of structural element determination, each episode can be represented as a time-ordered sequence of symbols with one symbol per structural element. Selecting and identifying valid structural elements for a program requires semantic interpretation of the structural elements detected via role recognition and temporal density filtering. This identification in turn requires minimal prior knowledge. For instance, a structural element corresponding to a sequence of white frames is a separator, while a long duration shot containing the dominant person at the beginning of the program is the conductor's opening.

Based on simple rules to identify valid structural elements, each episode is represented as a symbolic sequence depicting the succession of valid structural elements. The symbolic sequences corresponding to the different episodes of a program are usually similar due to the temporal stability of recurrent TV program structure. However, slight differences still exist between different episodes. Inferring a grammar from such sequences can be done by discovering the common patterns across symbolic sequences, a problem which is straightforwardly handled via grammatical inference. We adopt multiple sequence alignment techniques which can align the symbolic sequences in the way that alphabet symbols, i.e., valid structural elements, in a given position are homologous, superposable or play a common functional role. Many multiple sequence alignment tools have been developed, e.g., T-Coffee, MAFFT and ClustalW. We adopt in this work the ClustalW algorithm [START_REF] Thompson | Clustal w: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice[END_REF], which is one of the most widely used sequential tools for multiple sequence alignment due to its high accuracy, effectiveness and free availability [START_REF] Larkin | Clustal w and clustal x version 2.0[END_REF]. While more complex grammatical inference techniques exist, based on regular expressions or context free grammars [START_REF] Sakakibara | Efficient learning of context-free grammars from positive structural examples[END_REF], we limited ourselves to multiple sequence alignment to study the meaningfulness of symbolic representations derived in an unsupervised manner. The process of grammar induction from a symbolic representation is illustrated in Figure 4 with three episodes. Symbols, i.e., SGCDYE, represent the valid structural elements that were identified. A graphical representation of the resulting grammar was obtained using WebLogo [START_REF] Crooks | Weblogo: a sequence logo generator[END_REF]. A stack of symbols is used to illustrate each position in the grammar: The height of objects within the stack indicates the relative frequency of each symbol while the stack width is proportional to the fraction of valid symbols in that position.

IV. EXPERIMENTAL RESULTS

Experiments are conducted on three recurrent programs from different types, viz., game, news and magazine. Evaluation considers in turn the three steps of our method for structural grammar inference. We first measure performance of the event detectors considered. Second, we evaluate structural element determination. Finally, we discuss the grammar inferred for each of the three programs to assess their relevance.

A. Data set description

Three different programs, with 12 episodes each, are used for inference and evaluation, as given in Table I. Two programs, Que le meilleur gagne (GAME) and 20h News (NEWS), were taken with episodes selected over a large time period spanning 1991 to 2007. Que le meilleur gagne is a game show with four parts divided by separators. The program, leaded by a conductor, mainly contains interview scenes and questions/answers scenes with full text segments. The daily news show follows a standard pattern for such shows. The third program Thalassa (MAG) is a magazine about sea stories, where episodes were taken over a single year (1997). A conductor leads the show which is composed of reports and discussions. While the same conductor appears in all the episodes of GAME, two distinct conductors can be found both for NEWS and MAG.

B. Performance of broad scope detectors

Initial general purpose detectors are a key to subsequent steps and must therefore exhibit an acceptable level of accu- racy. We report here evaluation of dissolve transition detection and person clustering. Shot detection and monochrome image detection are based on standard techniques which yield very high accuracy. Performance for shot reverse shot detection is directly linked to performance of person clustering.

Results are presented in Table II. Dissolve detection is evaluated in terms of recall and precision. Detectors perform similarly for the three programs with correct recall and precision rates. Person clustering is evaluated by means of cluster purity. While correct purity values are obtained for GAME and MAGS, purity is rather low on NEWS. This is likely due to the fact that a fairly large number of persons appear in news programs and that scenes of reports in news are very variable with non discriminative clothing. Nevertheless, clustering results were found reliable enough for structure inference.

C. Structural elements detection

Selection of structural elements from the output of event detectors is evaluated both qualitatively and quantitatively.

Regarding temporal density filtering to select recurrent events, we observed for GAME that peaks in the density coincide for monochrome frames and for dissolve transitions, with a relatively consistent number of such regions, i.e., 3 or 4 per episode. For NEWS, monochrome images were found to be often around the same temporal positions. Additionally, two short sequences of monochrome images are found in each episode, resp. at the beginning and end of the episode. Positions of events and separators are illustrated in Figure 5. Based on their characteristics, such elements are considered as separators on both programs. For evaluation purposes, a separator is considered as correctly detected when overlapping with a reference separator as annotated in the data. Precision and recall in GAME are resp. 94 % and 67 %. In NEWS, where we have a stronger structure, a recall of 96 % is achieved with similar precision as in GAME. Dominant person detection succeeded in 83 % of the episodes for GAME, 92 % for NEWS and 75 % for MAG. NEWS are obviously easier with clear features identifying the anchorperson as the dominant speaker: fewer gestures, large area showing clothing, neutral and still facial expression, etc. In spite of relatively low cluster purity, dominant person detection is accurate. At the other end of the spectrum, MAG is a difficult content with long interviews for which occurrence time of the interviewee is almost as long as that of the anchor. Results in grammatical inference below indicate that limited accuracy in MAG did not hurt structure inference, even in spite of the limited number of episodes considered.

Moreover, identifying monologues of the dominant person turned out to be fairly easy based on the duration of the shots containing the dominant person. Dialog segments were also accurately determined combining person clustering and shot

D. Structural grammar inference

Results for grammar induction are illustrated in Figure 6 for the three programs. For NEWS, separators, denoted as S, are first determined. The segment between two separators, accounting for most time of the program, is considered as news content, denoted as N. The grammar of NEWS is therefore that of an introduction, followed by news reports, followed by a conclusion, a grammar shared by all shows. For MAG, selected symbols are based on dominant person's monologue and dialogs segments, yielding a simple deterministic grammar. A continuous segment with long duration, denoted N, is considered as a report while A and D represent anchorperson's monologue and dialogs respectively. For GAME, separators, dominant person (i.e., monologues of the conductor) and dialogs are the valid structural elements, resp. denoted S, D and A. The grammar inferred is more complex than for NEWS and MAG, reflecting the greater variability across shows. The main syntax is as follows: The game starts with an introduction (separator) followed by a dialog (between the anchor and the participants). We then have an alternating pattern of anchor (dominant person) and game phases (appearing as separator).

With very limited supervision, i.e., basic prior knowledge about TV program structure, possible structure is yielded for each program. All the identified structural elements in this ongoing work are the most common ones, so little bias caused by prior knowledge influences the final structural grammars. Obviously, all three grammars are concise because of the simple symbolic representation that was adopted. Yet, each one represents the structure of the corresponding program, thus demonstrating that grammar inference can efficiently handle structure inference in videos.Results on the game program interestingly prove that non deterministic video structures can be discovered. This last result opens the door to inferring structures at a finer grain. Considering symbolic description at a finer granularity will increase grammar diversity and complexity, which we believe can be handled via probabilistic grammar inference. Taking NEWS as an example, the news content, coarsely denoted N, can be divided into a repeating alternating an anchor's introduction and a report. This can be reflected in a grammar, either using multiple sequence alignment as considered here (assuming the number of reports is comparable across news episodes) or relying on more complex grammatical inference techniques with better factoring and generalization capabilities.

V. CONCLUSION Preliminary work described in this paper shows how a symbolic representation suited for grammatical inference can be obtained from a collection of episodes of the same program, with almost no supervision and no specific training data. Starting from a set of general purpose event detectors, structural elements are derived with minimal prior knowledge by exploiting role recognition and recurrence across episodes. Grammatical inference finally brings a final layer of abstraction by evidentiating the overall structure of the program from the joint analysis of multiple episodes. Experimental evaluation on three types of programs shows that coarse yet relevant structures can be discovered from examples, even for non deterministic programs structures.

Results reported here mostly hint that unsupervised video structuring in recurrent collections using grammatical inference is viable and deserves further attention. The framework proposed in this paper as a proof of concept remains general and can be extended in a number of directions. Obviously, obtaining a symbolic description at a finer grain with limited supervision has yet to be achieved. Increasing the number of general purpose detectors and targeting multiple modalities seems like the most natural path to follow. But adding detectors will challenge the determination of structural elements and the grammar induction step, requiring more elaborate grammars to be considered.

Fig. 1 .

 1 Fig. 1. General architecture of the three steps approach for the grammatical inference of a program structure.

Fig. 2 .

 2 Fig. 2. Flowchart for person clustering

Fig. 3 .

 3 Fig. 3. Example of temporal density filtering to select structural events corresponding to structure separators (from [1])

Fig. 4 .

 4 Fig. 4. Illustration of structural grammar induction from three episodes with symbols SGCDYE.

Fig. 5 .

 5 Fig. 5. Examples of separators for five different episodes of GAME and NEWS, where "+" in green (resp. blue) represents monochrome images (resp. dissolve) and "o" represents separators

Fig. 6 .

 6 Fig. 6. Grammars induced for resp. NEWS, MAG and GAME. See text for details.

TABLE I .

 I DESCRIPTION OF THE DATA USED FOR EVALUATION

	Dataset	Date	Episodes	Type	Average duration
	GAME	Sep. -Dec. 1991	12	Game	37.4 m
	NEWS	Jan. -Dec. 2007	12	TV news	36.9 m
	MAG	Jan. -Jul. 1997	12	Magazine	56.2 m

TABLE II .

 II PERFORMANCE OF DISSOLVE TRANSITION AND PERSON

			CLUSTERING
	Dataset	Prec.	Dissolve Rec.	F	Person Purity
	GAME	0.62	0.79	0.70	72.7%
	NEWS	0.64	0.81	0.71	49.5%
	MAGS	0.52	0.95	0.67	69.6%

ACKNOWLEDGMENT

The authors wish to acknowledge the help of Franc ¸ois Coste and Vincent Claveau, IRISA, for their advise. They in particular have been very useful in guiding the choices made regarding grammar induction.


Nabil H Mustafa
email: mustafan@esiee.fr

Saurabh Ray
email: saurabh@csa.iisc.ernet.in

Near-Optimal Generalisations of a Theorem of Macbeath

. Recently there have been some striking applications of Macbeath regions in discrete and computational geometry.

In this paper, we study Macbeath's problem in a more general setting, and not only for the Lebesgue measure as is the case in the classical theorem. We prove near-optimal generalizations for several basic geometric set systems. The problems and techniques used are closely linked to the study of ǫ-nets for geometric set systems.

Introduction

The goal of this paper is to study small, uniform-sized decompositions of geometric range spaces which approximate the range space. This can be seen as a discrete analogue and extension of the classical result of Macbeath [START_REF] Macbeath | A theorem on non-homogeneous lattices[END_REF] in convex geometry, as well as having several basic connections to well-studied problems in discrete geometry. Classical Macbeath Regions. Given a convex body K in R d of unit volume, and a parameter ǫ > 0, the theorem of Macbeath states the existence of disjoint convex bodies of K, each of volume Θ(ǫ), called Macbeath regions, such that any halfspace containing at least ǫ volume of K completely contains one of these convex objects. Formally, the following theorem follows from their work:

◮ Theorem 1 (Macbeath Regions). Given a convex body K ⊂ R d of unit volume, and a parameter 0 < ǫ < 1/(2d) 2d , there exists a set of convex objects M, |M| = O((1/ǫ) 1-2/(d+1) ), such that for any halfspace h with vol(h ∩ K) ≥ ǫ, there exists

K i ∈ M such that K i ⊂ h ∩ K and vol(K i ) ≥ 1 (6d) 3d vol(h ∩ K)
The existence of Macbeath regions was first proven in the paper of Macbeath [START_REF] Macbeath | A theorem on non-homogeneous lattices[END_REF], with several later applications to geometric problems. Edwald, Larmen and Rogers [START_REF] Ewald | The directions of the line segments and of the rdimensional balls on the boundary of a convex body in euclidean space[END_REF] used it for cap coverings, which was later further extended by Barany and Larman [START_REF] Barany | Convex bodies, economic cap coverings, random polytopes[END_REF] (also see Barany [3] for a survey of this and several other results). It was used for lower-bounds on range-searching by Bronniman, Chazelle and Pach [START_REF] Bronnimann | How hard is halfspace range searching[END_REF]. And very recently, Macbeath regions were used in an elegant way by Arya, Fonseca and Mount [START_REF] Arya | Optimal area-sensitive bounds for polytope approximation[END_REF] for computing near-optimal Hausdorff approximations to polytopes. licensed under Creative Commons License CC-BY Leibniz International Proceedings in Informatics Schloss Dagstuhl -Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany A fundamental and powerful result in computational geometry is the existence of small-sized ǫ-nets: given a set system (X, R), and a parameter ǫ, an ǫ-net is a subset X ′ ⊂ X such that X ′ ∩ R = ∅ for all R ∈ R where |R| ≥ ǫ|X|. The famous theorem of Haussler-Welzl [START_REF] Haussler | Epsilon-nets and simplex range queries[END_REF] shows that ǫ-nets of size O(d/ǫ log d/ǫ) exist for set systems (X, R), where d is the VC-dimension of the set system (X, R). This bound was later improved in [START_REF] Komos | Almost tight bounds for epsilon nets[END_REF] to an optimal bound of (1 + o( 1))( d ǫ log(1/ǫ)). By now ǫ-nets are an indispensable tool in combinatorics and algorithms [START_REF] Varadarajan | Weighted geometric set cover via quasi-uniform sampling[END_REF][START_REF] Chan | Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling[END_REF][START_REF] Kenneth | Improved approximation algorithms for geometric set cover[END_REF][START_REF] Aronov | Small-size ǫ-nets for axis-parallel rectangles and boxes[END_REF][START_REF] Pach | Tight lower bounds for the size of epsilon-nets[END_REF][START_REF] Pyrga | New existence proofs epsilon-nets[END_REF][START_REF] Arya | Optimal area-sensitive bounds for polytope approximation[END_REF][START_REF] Komos | Almost tight bounds for epsilon nets[END_REF][START_REF] Matousek | Reporting points in halfspaces[END_REF][START_REF] Chekuri | On the set multi-cover problem in geometric settings[END_REF].

Note that Macbeath's original theorem immediately implies an ǫ-net kind of a result: for any convex body C in R d of volume V , it is possible to pick O( 1 ǫ ) points in C which stab all halfspaces containing an ǫ-th fraction of the volume of C. However, the statement itself is much stronger than that: instead of just points, it gives us O( 1 ǫ ) regions of volume Θ(ǫV ) so that each halfspace containing an ǫ fraction of the volume of C contains one of the regions. The same kind of result is not true in general in a discrete setting (with counting measure instead of Lebesgue measure ) for halfspaces in R d . However, it is true for halfspaces in R 3 . Given n points in R 3 , one can find O( 1 ǫ ) groups containing Θ(ǫn) points each so that any halfspace containing ǫn points contains one of the groups. This is much stronger than just the existence of ǫ-nets of size O( 1ǫ ). This raises the intriguing question: of the large number of results known for ǫ-nets, which can be optimally strengthened like above? Combinatorial Macbeath Regions. Given the existence of decomposition of a convex set K into roughly equal-volume subsets with respect to halfspaces, the natural question is to prove the existence of a small-sized set of Macbeath regions for the counting measure (instead of the Lebesgue measure).

So the problem is: given a set P of n points in R d and a parameter ǫ > 0, one would like to construct sets P = {P 1 , . . . , P m }, P i ⊂ P , such that each set P i has size Ω(ǫn), and any halfspace containing at least ǫn points contains a set in P.

It turns out that this is implied by a classical result in discrete geometry, called shallow cuttings, which states the following [START_REF] Matousek | Reporting points in halfspaces[END_REF][START_REF] Chekuri | On the set multi-cover problem in geometric settings[END_REF]. Given a set of n regions S in R d and two parameters r, l, a (1/r, l)-shallow cutting w.r.t. S is a partition of R d into cells (of constant descriptive complexity) such that i) each cell is intersected by the boundary of at most n/r regions of S, and ii) the number of cells containing points of depth smaller than l is at most O((rl/n + 1) d • n/l • φ(n/l)). A set of regions is said to have union complexity φ(•) if the combinatorial complexity of the union of any r of the regions is at most rφ(r).

It can be observed that this statement implies a Macbeath-type statement for halfspaces, and more generally, for the following problem for regions of small union complexity: given a set of regions S of union complexity φ(•), the objective is to compute a family U of subsets of S, each of size Ω(ǫn), such that any point contained in at least ǫn objects of S hits all elements of some set in U.

To construct the Macbeath sets U for regions in S, fix l = 2ǫn, r = 2/ǫ, and construct a (1/r, l)shallow cutting for S. For a cell C in the shallow cutting, let r(C) be the set of regions in S that completely contain C, i.e., s i ∈ r(C) iff C ⊂ s i . Now, for all cells C that contain a point of depth at most 2ǫn (called shallow cells), add r(C) to U. By the shallow-cutting theorem, the number of cells containing a point of depth ǫn is

O((rl/n + 1) d • n/l • φ(n/l)) = O(4 d • 1/ǫ • φ(2/ǫ)) and so |U| = O(1/ǫ • φ(2/ǫ)).
To show that sets in U form the required Macbeath regions, recall that the cutting partitions R d into a set of cells such that each cell intersects the boundary of at most n/r = ǫn/2 objects in S. For a point p hitting ǫn regions, let C be the shallow cell containing p. By the property of shallow-cuttings, of the ǫn regions containing p, at most ǫn/2 regions can intersect C.

The remaining at least ǫn/2 regions must then completely contain C, and so for the r(C) added to U that contains p, we have |r(C)| ≥ ǫn/2.

The above shows the existence of O(1/ǫφ(1/ǫ)) sets such that any point contained in Θ(ǫn) sets of S must hit one of the constructed sets. To make it work for all sets of size at least ǫn, we can iteratively construct sets for increasing values of ǫ, i.e., ǫ, 2ǫ, . . . , 2 i ǫ, and take the union, still obtaining O(1/ǫφ(1/ǫ)) sets.

For our problem of halfspaces, simply dualize each point in P to a halfspace, and apply the above construction. For halfspaces, rφ(r) = O(r ⌊d/2⌋ ), and so we get the following combinatorial version of Macbeath: given a set P of n points in R d , there exists a set P = {P 1 , . . . , P m }, P i ⊂ P , with m =1 ǫ ⌊d/2⌋ , such that i) all sets in P have size Ω(ǫn), and ii) any halfspace containing ǫn points of P contains at least one set in P.

The existence of a number of other 'Macbeath-type' statements for several other range spaces is also implied by the above proof. In particular, for regions with linear union complexity, i.e., φ(r) = O(1), there exist linear-sized Macbeath regions. This points to the possibility of the existence of such structural partitioning properties for a wide range of sets derived from geometric objects. In this paper we initiate a systematic study of the analogues of Macbeath regions for other commonly studied geometric set-systems.

Our results.

Given a set system (X, R) and ǫ > 0, we say that a set system U over X is an ǫ-Macbeath net (or ǫ-Mnet for short) of (X, R) if i) each set in U has size Ω(ǫ|X|), and ii) for every set R ∈ R of size at least ǫ|X|, there exists a set U ∈ U such that U ⊆ R. The size of an ǫ-Mnet U is |U|. Parameterizing the problem a little further, if each set in U has size at least ǫn/k, we call it a 1 k -heavy ǫ-Mnet . In the study of ǫ-nets for geometric set systems, there are two types of set-systems that are frequently studied: each of these are defined by a set of points P , and a set of regions S. In the so-called 'primal' set-systems, P is taken as the ground set, and the subsets are induced by the regions in S, where a region R induces the subset R ∩ P . In the so-called 'dual' set-systems, S is taken as the ground set, and the subsets are induced by points in P , where a point p induces the subset consisting of the regions in S containing p. Often in the dual setting P is not mentioned, and is assumed to be the entire Euclidean space.

Earlier we pointed out the existence of ǫ-Mnets for halfspaces of size O(1/ǫ ⌊d/2⌋ ). Unfortunately this bound cannot be improved substantially: in Section 3, we show that it is not very far from optimal, that is for any d, there exist a set of n points in R d where any P satisfying conditions i) and ii) has size at least Ω(

1 ǫ ⌈(d-1)/3⌉ ).
The earlier statement in fact proved the existence of Macbeath sets for the dual problem for general regions in terms of their union complexity. Namely, it showed: ◮ Theorem (ǫ-Mnets for dual set-systems). Let S be a set of n regions in R d with union complexity φ(r) 1 . Then there exists an ǫ-Mnet for the dual set-system defined by S and R d (i.e., subsets of S hit by a point in the plane for the set system), of size O(

1 ǫ φ( 1 ǫ )).
Interestingly, the dependence of φ(•) in general cannot be reduced to, for example, log φ(•), as is the bound for ǫ-nets. A set-system which provides a counter-example follows from our first main result, which considers ǫ-Mnets for the commonly-studied range-space induced by axis-parallel rectangles in the plane. For these, we optimally tighten the result produced by shallow-cuttings by improving the upper-bound, and then providing a matching lower-bound. We prove the following in Section 2:

◮ Theorem 1 (ǫ-Mnet for rectangles in R 2 ). Let R be a set of n rectangles, P a set of n points in R 2 , ǫ > 0 a parameter, and k ≥ 2 an integer:

1. There exists a 1 2 k -heavy ǫ-Mnet for the dual set-system defined by R and R 2 , of size O(4 k /ǫ 1+1/k ). Furthermore, this cannot be significantly improved: there exists a set R of n axis-parallel rectangles such that any 1 k -heavy ǫ-Mnet for the dual set-system defined by R and R 2 has size Ω((1/ǫ) 1+1/(k-1) ).

2.

There exists an ǫ-Mnet for the primal set-system defined by P and R, of size O((1/ǫ) log 1/ǫ).

Furthermore, this cannot be significantly improved: there exists a set P of n points in R 2 such that any 1 k -heavy ǫ-M net for the primal set-system defined by P and R has size

Ω( 1 ǫ log k 1 ǫ ).
Our second main result is to consider the primal case, i.e., where the input is a set of points P , and the ranges are defined by geometric objects such as circles, k-sided polygons, and in general, objects of some fixed descriptive complexity. We prove the following in Section 3:

◮ Theorem 2. Let P be a set of n points in R 2 . Then one can construct ǫ-Mnets of size 2 :
O(1/ǫ) for sets induced by disks in the plane, O(1/ǫ) for sets induced by rectangles all intersecting a fixed line l, Õ(1/ǫ 2 ) for sets induced by lines, cones, strips in the plane, Õ(1/ǫ 3 ) for sets induced by triangles, and in general k-sided polygons in the plane (the constant in the asymptotic notation depends on k).

We further show in Section 3 that near-linear bounds (like those achieved for halfspaces in 2 and 3 dimensions, or for the dual set-systems of linear union-complexity) are not possible for even simple primal set-systems: there exist a set P of n points in the plane such that any ǫ-Mnet for lines must have size Ω(1/ǫ 2 ). This implies that for strips or cones in the plane, the same bound holds, ruling out near-linear bounds for even the simplest type of geometric objects.

We conclude our study by observing that the above series of results, while their proofs use different techniques, indicate an intriguing relation between the size of ǫ-nets and the size of ǫ-Mnets . In all cases, they obey the following: if for a range-space (dual, or primal), the ǫ-nets have size O(1/ǫf (1/ǫ)), then the size of ǫ-Mnets for the same range-space is O(1/ǫc f (1/ǫ) ), where c is constant. So for all spaces known to have linear-sized ǫ-nets (which is optimal), our proofs prove the existence of linear-sized ǫ-Mnets (which is optimal). For the primal set-systems of axis-parallel rectangles in the plane, the ǫ-nets have size O(1/ǫ log log 1/ǫ) (shown to be optimal) [START_REF] Aronov | Small-size ǫ-nets for axis-parallel rectangles and boxes[END_REF][START_REF] Pach | Tight lower bounds for the size of epsilon-nets[END_REF], and our result show ǫ-Mnets of size O(1/ǫ log 1/ǫ) (which we show to be optimal). And for the remaining ranges which have ǫ-nets of size O(1/ǫ log 1/ǫ), we show the existence of ǫ-Mnets of size O(1/ǫ c ). It would be interesting to see if there is any connection with the (still) open problem of finding the right bound on the size of ǫ-nets for lines in the plane.

Proof of Theorem 1

In this section we prove Theorem 1, which completely resolves the case for rectangles. We start by giving the lower-bounds for the primal and the dual problem, and then give the matching upper-bounds 2 Õ(•) ignores polylogarithmic factors.

for both.

Lower Bounds

The following Lemma gives the key insight to studying ǫ-Mnet for rectangles.

◮ Lemma 3. For any integers r, d ≥ 1, consider the grid G = [r] d in R d . Then the set system on G induced by incidences with axis-parallel lines can be realized by point-rectangle incidences in R 2 .

Proof. Let r ≥ 1 be any integer and let

[r] represent the set {0, • • • , r -1}. Let G = [r] d
which can be thought of as a finite d-dimensional grid of side length r. For some fixed integers

a 1 , • • • , a i-1 , a i+1 , • • • a d ∈ [r], consider the set of points S i (a 1 , • • • , a i-1 , a i+1 , • • • a d ) = {(a 1 , • • • , a i-1 , x, a i+1 , • • • a d ) : x ∈ [r]}.
We call such a set a line in direction i. There are dr d-1 lines : r d-1 in each of the d directions.

We will show that there exists a mapping π : G → R 2 s.t. for each line l (in any direction i), the smallest (inclusion minimal) axis parallel rectangle containing the image π(l) of the points in l does not contain the image of any other points of G. Here is the mapping π that we will use:

π((a 1 , • • • , a d )) = j a j v j
, where v j = (r j , r d+1-j ). For any point z ∈ G, we will interpret p = π(z) both as a vector and as a point, as suitable. When treating it as a vector we will denote it as p.

For any point p = (a 1 , • • • , a d ) ∈ G, let V <i (p)
denote the vector j<i a j v j and V >i (p) denote the vector j>i a j v j . Thus we can write π(p) as

V <i (p) + a i v i + V >i (p). Consider the line l = S i (a 1 , • • • , a i-1 , a i+1 , • • • a d ). The minimal rectangle R containing π(l) is defined by the two opposite corners π(u) and π(v), where u = (a 1 , • • • , a i-1 , 0, a i+1 , • • • a d ) and v = (a 1 , • • • , a i-1 , r -1, a i+1 , • • • a d )
are the extreme points in l. The width of R is (r -1)r i and its height is (r -1)r d+1-i .

Consider any point

z = (b 1 , • • • , b d ) ∈ G\l.
Let p = π(z) and let q be the point j =i a j v j +b i v i ∈ l.

Now, p -q = ( V <i (p) -V <i (q)) + ( V >i (p) -V >i (q)
). Since p = q, one of the summands must be non-zero. Without loss of generality assume that the latter summand is non-zero. The other case is symmetric.

Since the vector V >i (p)-V >i (q) is an integral combinations of the vectors v j , j > i, its x-coordinate has magnitude at least r i+1 . On the other hand the x-coordinate of ( V <i (p) -V <i (q)) has magnitude at most 1≤j<i (r -1)r j = r ir i-1 . Therefore, the horizontal distance between p and q is at least r i+1 -(r i -r i-1 ) which is greater than the width of R. Hence, p / ∈ R. When ( V <i (p)-V <i (q)) = 0, a similar argument holds for the y-coordinates of p and q showing that their vertical distance is larger than the height of R. ◭

Proof of Theorem 1 part 1) lower-bound. We now show that for any integer constant d ≥ 2, there exists a set R of n axis-parallel rectangles such that any 1 k -heavy ǫ-Mnet for R w.r.t. points has size Ω((1/ǫ) 1+1/(k-1) ).

Proof. Now apply Lemma 3 with d = k and r = ǫ -1 d-1 . Let G be the grid [r] d as before. We set P = {π(p) : p ∈ G} and we take R to be the set of rectangles with ǫn/d copies of each of the set R ′ of dr d-1 rectangles corresponding to the dr d-1 lines in G. Note that |R| = ǫn/d • dr d-1 = n. Since each of the points in G is contained in d lines (one in each direction), the points in P are contained in d rectangles of R ′ and consequently ǫn rectangles of R. Since there is at most one line through two points in G there is at most one rectangle in R ′ , and hence at most ǫn/d rectangles of R that contain any pair of points p, q ∈ P . Since for any 1 k -heavy ǫ-Mnet U, each U ∈ U has size more than ǫn/k, it must be that no set in U can be contained in two sets R(p) and R(q) induced by two distinct points p and q in P . Therefore

|U| ≥ |P | = r d = ǫ -k k-1 . ◭
Proof of Theorem 1 part 2) lower-bound. We now show that for any integer constant k ≥ 2, there exists a set P of n points in R 2 such that any 1 k -heavy ǫ-M net of P , w.r.t. axis-parallel rectangles, has size Ω(

1 ǫ log k 1 ǫ ).
Proof. Apply Lemma 3 with r = k, and d such that r d-1 = 1 ǫ . Let R be the set of dr d-1 = 1/ǫ log k 1/ǫ rectangles corresponding to the lines of G, and let P be the set of points with ǫn/r copies of each π(p), ∀p ∈ G. Each of the rectangles in R contains rǫn/r = ǫn points of P . Any two rectangles of R share at most ǫn/r = ǫn/k points of P . Thus no two rectangles in R may share the same set U ∈ U of a 1 k -heavy ǫ-M net U. Since each of them must contain some U ∈ U, we have |U| ≥ |R| and the result follows. ◭

Upper Bounds

We now give constructions which match the preceding lower-bounds to complete the proof of Theorem 1 part 1. Our argument is based essentially on the technique of boot-strapping; at the cost of worse constant factors, we give a simple exposition below.

Construct a hierarchical subdivision of the rectangles in R by vertical lines, with an integer k = 1/ǫ 1/d , as follows. Let n i = n/k i , and ǫ i = ǫ(k/2) i . At the 0-th level (i = 0), let l 0 1 , . . . , l 0 k by a set of k vertical lines such that the number of rectangles of R lying between two consecutive lines ('a slab') is at most n/k. Let R 0 j be the set of rectangles lying entire in the j-th slab. For each line l 0 j , construct a ǫ i /4-Mnet for all of the (at most) n rectangles of R intersecting it. Furthermore, recursively construct a ǫ i+1 -Mnet for the rectangles in R 0 j for each j. The recursive construction continues for d steps, where at the i-level, there are k i total subproblems, each subproblem has at most n i = n/k i rectangles, and with ǫ i = ǫ(k/2) i . Finally we use a direct O(1/ǫ 2 d )-sized construction for the ǫ d -Mnet of the final k d subproblems at level i = d: construct 10/ǫ d vertical and horizontal lines so that each vertical and horizontal slab contains at most ǫ d n/10 rectangles, and for each grid cell c, add to U any ǫ d n d /2 rectangles containing c (if possible). Now notice that any point in ǫ d n d rectangles must have at most ǫ d n d /5 rectangles intersecting the cell boundary in which it lies, and so at least ǫ d n d /2 of the remaining ones would form a set in U. The next two claims show that all these Mnet together form a ǫ-Mnet U for R of the required size, and we're done.

◮ Claim 1. Each set in U has size Θ(ǫn/2 d ). The size of U is O(4 d /ǫ 1+1/d ).
Proof. At the i-level there are k i subproblems, each of size at most n i = n/k i with ǫ i = ǫ(k/2) i . For each such subproblem, we partition its n i rectangles by k lines, and construct a ǫ i /4-Mnet for the rectangles intersecting of these k lines. Note that the set of rectangles intersecting any line, and clipped to one side of the line have linear union complexity and by our Theorem on the dual setsystems, there exists a ǫ i /4-Mnet of size O(1/ǫ i ). Hence the total size over all internal subproblems is:

d i=0 k i • k • O( 1 ǫ i ) = d i=0 k i+1 • O( 2 i ǫk i ) = d i=0 O( 2 i ǫ 1+1/d ) = O( 2 d ǫ 1+1/d )
After d steps, we have k d subproblems, each with at most n/k d rectangles, and ǫ d = ǫ(k/2) d . Now just use a direct construction which constructs an ǫ-Mnet of size O(1/ǫ 2 ), to get the total size of Mnet at the last step to be O(

k d ǫ 2 d ) = O( 4 d ǫ 2 k d ) = O(4 d /ǫ).
At any level i, we construct a ǫ i -Mnet on a set of at most n/k i rectangles. So each set in the Mnet has size

ǫ i • n/k i = O(ǫn/2 i ). ◭ ◮ Claim 2.
Each point in at least ǫn rectangles of R contains a set of U.

Proof. Take a point q lying in at least ǫn rectangles of R. At the 0-th level, say q lies in the vertical slab defined by lines l 0 j and l 0 j+1 . If q hits at least ǫn/4 rectangles intersected by either l 0 j or l 0 j+1 , say l 0 j , then it hits at least ǫn/4 rectangles out of a total of at most n rectangles intersected by l 0 j . So the (ǫ i /4 = ǫ/4)-Mnet for l 0 j will have a set contained by q. Otherwise q hits at least ǫ 0 n 0 /2 = ǫn/2 = ǫ(k/2)(n/k) = ǫ 1 n 1 rectangles of the set R 0 j of size n 1 = n 0 /k, and we proceed to this subproblem.

In general, at the i-level, each subproblem has n i = n/k i rectangles, with ǫ i = ǫ(k/2) i . Then either q hits at least ǫ i • n i /4 rectangles intersecting one of the lines, and so will contain a set from the ǫ i /4-Mnet constructed for each of the k vertical lines. Or q contains at least ǫ i n i /2 rectangles out of a total of n i /k rectangles lying in one of the slabs defined by the k vertical lines. But as

ǫ i n i /2 = ǫ/2 • (k/2) i • n/k i = ǫ(k/2) i+1 n/k i+1 = ǫ i+1 n i+1
q will be covered inductively by the ǫ i+1 -Mnet constructed for the n i+1 = n/k i+1 rectangles in one of the resulting subproblems at level i + 1. ◭

Finally we present the tight upper-bound for the primal case of axis-parallel rectangles in Theorem 1 part 2.

Assume P = {p 1 , . . . , p n } are sorted by their x-coordinates. Given P , construct the balanced binary subdivision of P with vertical lines: divide P by a vertical line into two equal-sized subsets P 0 0 , P 0 1 , and then recursively divide each of these sets for log 1/ǫ levels. Let P i j be the j-th resulting subset of P at level i, i.e., P i j = {p jn/2 i , . . . , p (j+1)n/2 i -1 }. For each set P i j , and for each of its two bounding lines l 0 and l 1 in the binary subdivision above, construct a 2 i-1 ǫ-Mnet for the following primal set-system: the base set is P i j , and given the line l ∈ {l 0 , l 1 }, the sets are induced by rectangles intersecting the line l. Note that all points of P i j lie on the same side of l. Let U be the union of all these Mnets . By Theorem 2, a ǫ-Mnet for such a set-system has size O(1/ǫ).

We now prove that U is an ǫ-Mnet of P , w.r.t. axis-parallel rectangles, of size O(1/ǫ log 1/ǫ). ◮ Claim 3. Each set in U has size Θ(ǫn), and size of U is O(1/ǫ log 1/ǫ).

Proof. P i j has n/2 i points, and so a

(2 i-1 ǫ)-Mnet of P i j has sets of size O(2 i-1 ǫ • n/2 i ) = O(ǫn). Each such 2 i-1 ǫ-Mnet has size O(1/2 i ǫ)
, there are 2 i sets P i j at level i, and a total of log 1/ǫ levels. Hence the size of

U is O(1/2 i ǫ • 2 i • log 1/ǫ) = O(1/ǫ log 1/ǫ). ◭ ◮ Claim 4.
Each axis-parallel rectangle containing ǫn points of P contains a set of U.

Proof. Let R be an axis-parallel rectangle containing ǫn points of P . Let i be the smallest index such that R intersects exactly one vertical line separarting two sets P i j and P i j+1 at level i. Say R intersects the line l separating P i j and P i j+1 . Then R must contain at least ǫn/2 points from either P i j or P i j+1 , say P i j . Let R ′ be the part of R on the side of l towards P i j . All such R ′ form a set of psuedo-disks, and so R ′ must contain at least one set of the 2 i-1 ǫ-Mnet for P i j , as

|R ∩ P i j | = |R ′ ∩ P i j | ≥ ǫn/2 = 2 i-1 ǫ • n/2 i = 2 i-1 ǫ • |P i j | ◭ 3 Proof of Theorem 2
In this section we give the proof of Theorem 2. Given a set P of n points, first we give the proof for the most difficult case, that of the primal set-system induced by triangles, and in general, k-sided polygons in the plane. At the end we sketch out the modifications required for the rest of the cases of strips, cones and disks.

So we are given a set P of n points, and its subsets induced by the family of all k-sided polygons. The objective, as before, is to compute a small-sized ǫ-Mnet . We will assume P to be in general position.

Since a k-sided polygon can be triangulated with k triangles, any k-sided polygon containing ǫn points of P also contains a triangle containing ǫn/k points. Hence an ǫ/k-Mnet with respect to triangles is an ǫ-Mnet with respect to k-sided polygons. We can therefore restrict ourselves to triangles.

Consider any triangle T in the plane that contains ǫn points of P . By moving the sides of the triangle we can ensure that each side of T contains at least two points of P and this can be done in such a way that no point outside T enters the interior of P . Some points in the interior of T may have moved to its boundary and some point outside T may also have moved to the boundary. Since at most 6 points may be on the boundary of T , due to P being in general position, the interior of T still contains at least ǫn/2 points assuming ǫn ≥ 12. For ǫn < 12, the set P itself is an ǫ-Mnet . Thus we can further restrict ourselves to the interior of triangles each of whose sides contain at least two points. Figure 1 shows a triangle with each side containing two points of P . The points q and r could be identical, they could both be equal at the corner b of the triangle. Similarly s and t could be at c and u and p could be at a. Observe that the triangles aqt, bsp, cur and prt cover the triangle T and therefore one of them must contain at least ǫn/4 points of P . Each of these triangles are of the following type: at least two of the corners are in P and all sides contain at least two points of P . We call such triangles anchored triangles. Thus we can again restrict ourselves to the problem of anchored triangles containing ǫn points.

Let O be the set of all anchored triangles. Let O ′ = {o 1 , . . . , o t } be a maximal set of t triangles from

O such that o i ∩ P = ǫn and |o i ∩ o j ∩ P | ≤ ǫn/2. ◮ Claim 5. |O ′ | ≤ 2 • f ( c ǫ • log 1/ǫ, 2c log 1/ǫ)
, where f (n, l) is the maximum number of ≤ l-sized subsets induced by objects in O given any set of n points, and c is some fixed constant.

Proof. The proof is via the probabilistic method. Pick each point of P independently at random with probability p = c/(2ǫn) • log 1/ǫ to get a random sample S.

◮ Fact 1. With probability at least 1/2, the sets o i ∩ S, i = 1 . . . t, are distinct and |S| ≤ c/ǫ • log 1/ǫ.

Proof. Consider the range space (P, R ′ ), where

R ′ = {(o i \ o j ) ∩ P | ∀1 ≤ i < j ≤ t}.
First note that from the definition of O ′ , we get that each set in R ′ has size at least ǫnǫn/2 = Θ(ǫn). Second, we use the fact that ranges induced by polygons with k sides have VC-dimension at most 2k + 1 [START_REF] Matousek | Lectures in Discrete Geometry[END_REF]; it is easy to see that R ′ is a subset of the ranges induced by polygons (or union of polygons) with at most 9 sides (overall), and so the VC-dimension of R ′ is at most 19. Then by the Haussler-Welzl theorem [START_REF] Haussler | Epsilon-nets and simplex range queries[END_REF], for c > 19 • 4, with probability at least 3/4, S is an ǫ-net for (P, R ′ ). Now observe that if o i ∩ S = o j ∩ S, then the set (o i \ o j ) ∩ S is empty, a contradiction to the fact that S is an ǫ-net for R ′ .

Finally, from standard concentration estimates from Chernoff bounds, it follows that |S| ≥ c/ǫ•log 1/ǫ with probability at most 1/4. ◭

For each o i ∈ O ′ , let X i be the random variable which is 1 if |o i ∩ S| ≥ 2c log 1/ǫ, and 0 otherwise. Then ◮ Fact 2. With probability greater than 1/2, X i ≤ t/2.

Proof.

For a fixed i, by linearity of expectation:

E[|o i ∩ S|] = c/2 • log 1/ǫ By Markov's inequality applied to each X i , P r[X i = 1] = P r[|o i ∩ S| ≥ 2c • log 1/ǫ] = P r[|o i ∩ S| ≥ 4 • E[|o i ∩ S|]] ≤ 1/4
Hence the expected value of Y = X i is:

E[ X i ] = E[X i ] = P r[X i = 1] ≤ t/4
By Markov's inequality applied to Y , we get that Proof. The proof is folklore, and follows by standard application of the Clarkson-Shor method [START_REF] Matousek | Lectures in Discrete Geometry[END_REF].

P r[ X i ≥ t/2] ≤ E[ X i ]/(t/
For completeness we sketch it here. An anchored triangle abc can be of two types -either all corners are in P or exactly two corners, say a and b, are in P and there is a point p ∈ P on ac and another point q ∈ P on bc. The number of anchored triangles of the first type is clearly at most n 3 . Thus we only need to bound the number of anchored triangles of the second type with at most l points in the interior. We first consider the case when l = 0, i.e., anchored triangles of the second type with no point of P in the interior. For such triangles, observe that fixing the points a, b and p determines q. If there were two points q and q ′ then it can be easily shown that one of anchored triangles T 1 determined by a, b, p and q and T 2 determined by a, b, p and q ′ is non-empty -either T 1 contains q ′ or T 2 contains q. Thus the number of such triangles is at most n 3 . Let N denote the number of anchored triangles of the second type with at most l points in the interior. Let Q be a subset of P obtained by picking each point of P independently with probability p = 1/l. The expected number of empty anchored triangles of the second type determined by Q is at most the expected number of triples in Q which is p 3 n 3 since every triple in P appears as a triple in Q with probability p 3 . At the same time, each of the N anchored triangles with at most l points in the interior becomes an empty anchored triangles in Q with probability p 4 (1p) l . Thus the expected number of empty anchored triangles in Q is at least N p 4 (1p) l . Thus N p 4 (1p) l ≤ p 3 n 3 . Since p = 1/l, it follows that N = O(ln 3 ). ◭

Triangles and k-sided polygons. Finally, the proof for the size of ǫ-Mnet for triangles and k-sided polygons follows from Claims 5, 6 and 7. We now sketch the proof of the other cases along the above lines.

Lines, strips, cones. For sets induced by lines, strips, cones in the plane, one can follow the above proof. The function f (n, l) correspondingly denotes the number of subsets of size l induced by the objects of the appropriate type (lines, strips, cones). For lines, f (n, l) = O(n 2 ), for strips it is O(n 2 l) and for cones it is O(n 2 l 2 ). The proof then follows from the above claims.

Rectangles intersecting a common line l. As each rectangle contains ǫn points and intersects l, for each rectangle R, take the portion of the rectangle on the side of l that contains at least ǫn/2 points. We can construct ǫn/2-Mnets for the two sides of l separately.

So consider the rectangles anchored on l lying on the same side containing ǫn/2 points of P . Call this set O. As before, let O ′ be the maximal subset of O such that i) every pair of rectangles in O ′ share at most ǫn/10 points, and ii) each rectangle contains ǫn/2 points. These form pseudo-disks (i.e., no two rectangles pierce each other) and by the result of [START_REF] Pyrga | New existence proofs epsilon-nets[END_REF], |O ′ | = O(1/ǫ). Now Claim 6 implies that one can construct ǫ/2-Mnet of size O(1/ǫ).

Disks. By standard Veronese map, points P and disks D can be lifted to halfspaces H in R 3 such that each point is lifted to a point in R 3 and each disk is lifted to a halfspace in R 3 in such a way that their incidences are preserved. Now the required bound follows from the result for halfspaces in R 3 .

Lower-bounds.

◮ Theorem 4. For every ǫ > 0 and k an integer, there exists a set P of n points in the plane, and a set D of Ω( 1 ǫ d+1 ) curves of degree at most d, such that i) each curve contains ǫn points of P and, ii) no two curves share more than ǫn/k points of P . ǫ(d+1)(dk) i ) = Ω( 1 ǫ d+1 ) of these polynomials. Since for each value of x ∈ [dk], the value of y is in [ 1 ǫ ], each of these curves contain dk points of G. Also, since these are curves of degree at most d, no two intersect in more than d points. Let P be the set of n points containing ǫn/dk copies of each of the points in G. We thus get a set of Ω( 1 ǫ d+1 ) curves of degree at most d, each of which contain ǫn points of P and no two of which share more than ǫn/k points of P . ◭ ◮ Corollary 5. This gives a lower bound of Ω( 1 ǫ d+1 ) for 1 k -heavy ǫ-M nets for range spaces induced by curves of degree at most d in the plane.

Note that this immediately implies that for sets induced by lines in the plane, ǫ-Mnets must have size Ω(1/ǫ 2 ). Which in turn is a special case for strips and cones in the plane.

◮ Corollary 6. Any ǫ-Mnet for sets induced by lines, strips and cones in the plane must have size Ω(1/ǫ 2 ).

Finally, using standard linearization [START_REF] Matousek | Lectures in Discrete Geometry[END_REF] (with Veronese maps), it is possible to lift a set of polynomial curves of degree d and a set of points to R 3d+2 so that each point in the plane is lifted to a point in R 3d+2 and each curve is lifted to a halfspace (i.e., the curve y = f (x) becomes (yf (x)) 2 ≤ 0, and each monomial of this expansion can be treated as a different coordinate for the linearization).

Figure 1

 1 Figure 1The union of triangles aqt,bsp, cur and prt covers the triangle abc.

Proof.

  For the lower-bound on the size of 1 k heavy ǫ-M net, consider the grid G = [dk] × [ 1 ǫ ] in the plane for some d ≥ 1, where [r] denotes the set {0, • • • , ⌈r⌉ -1}. Now, consider univariate functions of x of the form y = d i=0 a i x i where each a i is an integer in [ 1 ǫ(d+1)(dk) i ]. Clearly there are at least Ω( d i=0 1

  Thus we have the following: ◮ Corollary 7. Any ǫ-Mnet for sets induced by halfspaces in R d must have size Ω( 1 ǫ ⌈(d-1)/3⌉ ).

  So with probability greater than 1/2, at least half the sets of O ′ contain at most 2c log 1/ǫ points of S. ◭ Therefore, putting together Fact 1 and Fact 2, there exists a subset S of size (c/ǫ) log 1/ǫ such that o i ∩ S are distinct for all objects in O ′ , and for at least |O ′ |/2 of the objects in O ′ , we have|o i ∩ S| ≤ 2c log 1/ǫ.Let f (n, l) be the number of distinct subsets of size at most l that can be achieved by intersection with objects in O. These are called ≤ l-sets (the most extensively studied case is for halfspaces in R d ). So in our case above, each o i ∩ S formed by these |O ′ |/2 objects is a ≤ l-set of S, where l = 2c log 1/ǫ. By the bound on number of ≤ l-sets for k-sided polygons, we get|O ′ |/2 = f (|S|, l) = f ((c/ǫ) log 1/ǫ,2c log 1/ǫ) This gives the required bound on |O ′ |. ◭ Take this set O ′ of maximal objects, each containing ǫn points of P , and every pair of objects in O ′ intersecting in less than ǫn/2 points. For each object o i ∈ O, do the following: apply the simplicial partition theorem to o i ∩ P with the parameter t, which is a large enough constant, to get a partition of o i ∩ P into t sets of size Θ(|o i ∩ P |/t). Add each of these t sets to the ǫ-Mnet U for P . ◮ Claim 6. U is an ǫ-Mnet for the primal set-system defined by P and O, of size O(|O ′ |). First note that each set added to U had size Θ(|o i ∩ P |/t) = Θ(ǫn). And the number of such sets is O(|O ′ | • t) = O(|O ′ |). It remains to show that any object containing ǫn points of P contain one set of U. Take any object o containing ǫn points of P . By the maximality of O ′ , there exists o i ∈ O ′ such that |o ∩ o i | ≥ ǫn/2. Furthermore, of all the sets in the simplicial partition of o i , each edge of ∂o can intersect only O( √ t) sets; so in total the boundary of o can intersect at most O(3 √ t) sets. Each of these sets has O(|o i ∩ P |/t) points. So these sets can contribute at most O(3 √ t • |o i ∩ P |/t) points of o i to the object o. Setting t to be a large-enough constant (say, t = 37), this is less than ǫn/2. Therefore o must contain a point in o i which lies in a partition for o i not intersecting ∂o, i.e., the partition lies completely inside o.

	Proof.
	2) ≤ 1/2

◭ ◮ Claim 7. f (n, l) ≤ ln 3 .

And satisfying certain technical conditions of bounded algebraic complexity. See[START_REF] Kenneth | Improved approximation algorithms for geometric set cover[END_REF] for a broader discussion on this.