{'fraction_non_alphanumeric': 0.04521324863883847, 'fraction_numerical': 0.012726860254083485, 'mean_word_length': 4.268435520497191, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Planar Visibility Counting

For a fixed virtual scene (=collection of simplices) S and given observer position p, how many elements of S are weakly visible (i.e. not fully occluded by others) from p? The present work explores the trade-off between query time and preprocessing space for these quantities in 2D: exactly, in the approximate deterministic, and in the probabilistic sense. We deduce the EXISTENCE of an O(m^2/n^2) space data structure for S that, given p and time O(log n), allows to approximate the ratio of occluded segments up to arbitrary constant absolute error; here m denotes the size of the Visibility Graph--which may be quadratic, but typically is just linear in the size n of the scene S. On the other hand, we present a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k) preprocessing time and space with similar approximation properties and query time O(k*polylog n), where k<n is an arbitrary parameter. We describe an implementation of this approach and demonstrate the practical benefit of the parameter k to trade memory for query time in an empirical evaluation on three classes of benchmark scenes.


Motivation and Introduction
Back in the early days of computer graphics, hidden surface removal (and visible surface calculation) was a serious computational problem: for a fixed virtual 3D scene and given observer position, (partition and) select those scene primitives which are (and are fully) visible to the observer. Because of its importance, this problem has received considerable scientific attention with many suggestions of deep both combinatorial and geometric algorithms for its efficient solution. The situation changed entirely when the (rather unsophisticated) z-buffer algorithm became available in common consumer graphics cards: with direct hardware support and massive parallelism (one gate per pixel), it easily outperforms software-based approaches with their (usually huge factors hidden in) asymptotic big-Oh running times [McKe87]. For a fixed resolution, the z-buffer can render scenes of N triangles on-line in time essentially linear in N with a small constant. However even this may be too slow in order to visualize virtual worlds consisting of several hundreds of millions of triangles at interactive frame rates. Computer graphics literature is filled with suggestions of how to circumvent this problem; for example by approximating (in some intuitive, informal sense) the observer's views. Here, the benefit of a new algorithm is traditionally demonstrated by evaluating it, and comparing it to some previous 'standard' algorithm, on few 'standard' benchmark scenes and on selected hardware. We on the other hand are interested in algorithms with provable properties, and to this end restrict to 1.1 Conservative Occlusion Culling Definition 1. Objects which are hidden to the observer behind (possibly a collection of ) other objects may, but need not, be filtered from the stream sent to the rendering hardware, whereas any at least partially visible object must be visualized.
Here, "conservative" reflects that the rendering algorithm must not affect the visual apprearance compared to the bruce-force approach of sending all objects to the hardware. Occlusion culling can speed up the visualization particularly of very large scenes (e.g. virtual worlds as in Second Life or World of Warcraft) where, composed from literally billions of triangles, typically 'just' some few millions are actually visible at any instant. Other scenes, or viewpoints within a scene, admit no sensible occlusion; for instance the leaves of a virtual forest naturally do not fully screen sight to the sun or to each other, similarly for CAD scenes of lattice or similar constructions. In such cases, spending computational efforts on occlusion culling is futile and actually bound to a net performance loss. Between those extremes, and particularly for an observer moving between occluded and free parts of a large scene, the algorithmic overhead of more or less thoroughly filtering out hidden primitives generally trades off against the benefit in reduced rendering complexity. Put differently: Graphics hardware taking care of the visibility problem anyway opens the chance to hybridize with software performing either coarse (and quick) or careful (and slow) culling and leave the rest to the z-buffer.

Adaptive Occlusion Culling
It is our purpose is to explore this trade-off and to make algorithms adapt to each specific virtual scene and observer position in order to exploit it in a well-defined and predictable way. To this end we propose so-called visibility counts (the number of primitives weakly visible from a given observer position) as a quantitative measure of how densely occluded a rendering frame is, and whether and by how much occlusion culling therefore can be, expected to pay off. For technical reasons employed in Sections 2.6 and later, the formal notion slightly more generally captures the visibility of 'target' scenes through 'occluder' scenes: For scenes S and observer positions x with V(S, x, S) ≪ Card S, occlusion culling is likely to pay off; whereas for V(S, x, S) ∼ = Card S it is not. Quantitatively we have the following Hypothesis 3. Each culling algorithm A can be assigned a threshold function θ A (n) ∈ [0, 1] such that, for scenes S and observer positions x with visibility ratios V(S, x, S)/ Card(S) (significantly) beyong θ A (n), it yields a net rendering benefit and (significantly) below does not.

Combinatorial Geometry and Randomized Computation
Adaptivity constitutes an important issue in Computational Geometry; for instance in the context of Range Searching problems whose running time is preferably output sensitive, i.e. of the form O f (n) + k where n denotes the overall number of objects and k those that are actually reported; compare [Chaz86].
Adaptivity is of course a big topic in computer graphics as well. However this entire field, driven by the impetus to quickly visualize (e.g. at 20fps) concrete scenes in newest interactive video games, generally focuses on innovative heuristics and techniques at a tremendous pace. We on the other hand are interested in algorithms with provable properties based on formal and sound analyses and in particular with respect to well-defined measures of adaptivity. This of course calls for an application of computational and combinatorial geometry [BKOS97,Edel87].
Paradigm 4 (Computational Geometry in Computer Graphics). For interactive visualization of very large virtual scenes of size N 10 7 , algorithms must run in sublinear time O(N α ), α < 1, using preprocessed data structures of almost linear space O(N 1+ǫ ), ǫ ≪ 1, provably! Here (time and) space complexity refers to the number of (operations on) unit-size real coordinates used (performed) by an algorithm-as opposed to, e.g., rationals of varying bitlength ⋆ ⋆ ⋆ . Also visibility is considered in the geometric sense (as opposed to e.g. pixel-based notions): point q is visible from observer position p if both can be connected by an ideal light ray (=straight-line segment not intersecting any other part of the scene), recall Definition 2. Our algorithm features a parameter 1 ≤ ℓ < n to trade preprocessing space for query time.
Randomized algorithms are quite common in computer science for their efficiency and implementation simplicity. They have also entered the field of computer graphics. Here these techniques are employed to render only a small random sample of the (typically very large) scene in such a way that it appears similar to the entire scene [WFP*01,KKF*04,WW*06]. Our goal, on the other hand, is to approximate the count of visible objects (Definition 2), not their appearance.

Visibility
Visibility comprises a highly active field of research, both heuristically and in the sound framework of computational geometry [CCSD03]. Particularly the latter has proven combinatorially and algorithmically non-trivial already in the plane [ORou87,Ghos07]. Here the case of (simple) polygons is well studied [CAF07]; and so is point-point, point-segment, and segment-segment visibility for scenes S of n non-crossing line segments, captured e.g. in the Visibility Graph data structure [GhMo91]. Its nodes correspond either to segments or to segment endpoints (or to both: a bipartite graph); and two nodes get joined by an edge if one can partly see the other. Weak segment-segment visibility for instance amounts to the O(n 2 ) questions (namly for each pair of segments A and B) of whether there exist points a ∈ A and b ∈ B such that a is visible from b.
We, too, ask for weak segment visibility; however in our case the observer is not restricted to positions on segments of the scene but may move freely between them. For instance we shall want to efficiently calculate visibility counts for singleton targets V(S, x, {T }): ⋆ ⋆ ⋆ See however Item d) in Section 5 below Problem 5. Fix a collection S of non-intersecting segments in the plane and one further segment T . Preprocess (S, T ) into an almost linear (or merely worst-case subquadratic) size data structure such as to decide in sublinear time queries of the following type: Given x ∈ R 2 , is T (partly) visible through S ? Sections 2.1, 2.2, and 2.3 recall two algorithms that meet either the space or the time requirement but not both.

Overview
An empirical verification of Hypothesis 3 in dimensions 2, 2 1 2 , and 3, is the subject of a separate work [FJZ09]. Our aim here is to explore the complexity of calculating the visibility counts, thus providing rendering algorithms with the information for deciding whether to cull or not. In view of the large virtual scenes and the high frame rates required by applications, we have to consider both computational resources, query time and preprocessing space, simultaneously. Section 2 focuses on the problem of calculating visibility counts exactly, mostly based on the Visibility Space Partition; our main result here is a preprocessing algorithm with output-sensitive running time. Section 3 weakenes the problem to approximate calculations: first showing the existence of a rather small data structure with logarithmic query time in Section 3.1. However this data structure seems hard to construct in reasonable time, therefore Sections 3.2ff consider approaches based on random sampling. Section 4 describes an implementation and evaluation of this algorithm.

Exact Visibility Counting
This section recalls combinatorial worst-case approaches for calculating visibility counts according to Definition 2. Many efficient algorithms are known for visibility reporting problems, that is for determining the view of an observer [Pocc90]; however since reporting may involve output of linear size, such aproaches are generally inappropriate for our goal of counting in sublinear time. On the other hand, logarithmic time becomes easily feasible when permitting quartic space in the worstcase based on the Visibility Space Partition (VSP). The main result of this section, Theorem 13 yields an output-sensitive time algorithm for computing the VSP of a given set of line segments in the plane.

Reverse Painter's Algorithm
Prior to the hardware z-buffer, Painter's Algorithm was sometimes considered as a means to hidden surface elimination (at least in the 2D case): Draw all objects in back-to-front order, thus making closer ones paint over (and thus correctly cover) those further away. This of course relies on being able to efficiently find such an order: which is easily seen impossible in general unless we 'cut' some objects. Now two-dimensional BSP Trees provide a means to find such an order and a way to cut objects appropriately without increasing the overall size too much. We report from [BKOS97, Section 12]: Fact 6. Given a collection S of n non-crossing line segments in the plane, a BSP Tree of S can be constructed in time and space O(n · log n). Now instead of drawing the cut segments in back-to-front order (relative to the observer), feeding them into an Interval Tree in front-to-back order reveals exactly which of them are weakly visible and which not. Since insertion into an Interval Tree of size n takes time O(n · log n) we conclude [TeSe91]: Lemma 7. Given a collection S of n non-crossing line segments in the plane and an observer position x ∈ R 2 , V(S, x, S) can be calculated in time O(n · log 2 n) and space O(n · log n).
Notice that preprocessing S into a BSP Tree accelerates the running time 'only' by a constant factor.

Rotational Sweep
One can improve Lemma 7 by a logarithmic factor: Lemma 8. Given a collection S of n non-crossing line segments in the plane and an observer position x, V(S, x, S) can be calculated in time O(n · log n) and space O(n).
Proof. Sketch First mark all segments invisible. Then consider the 2n endpoints of S in angular order around x while keeping track of the order of the segments according to their proximity to the observer, the closest one thus being visible: whenever a new segments starts insert it into an appropriate data structure in time O(log n), whenever one ends remove it. Since the initial sorting also takes time O(n · log n), we remain within the claimed bounds.
⊓ ⊔ Nevertheless the running time still fails to meet Paradigm 4. Also, these approaches seem to offer no way to take advantage of a singleton target for the purpose of Problem 5.

Visibility Space Partition
Lemmas 7 and 8 work without any, and do not benefit asymptotically from, preprocessing of the fixed scene S. On the other hand by the so-called locus approach-storing all visibility counts in a Visibility Space Partition (VSP)-they can later be recovered in logarithmic running time [Schi01]: Lemma 9. a) For a collection S of n non-crossing line segments in the plane, there exists a partition of R 2 into O(n 4 ) convex cells such that, for all observer positions x ∈ C within one cell C, V(S, ·, S) is the same. b) The data structure indicated in a) and including for each cell its corresponding visibility count V(S, C, S) uses storage O(n 4 · log n) and can be computed in time O(n 5 · log n). Then given an observer position x, its corresponding cell C, and the associated visibility count, can be identified in time O(log n). c) When charging only real data and operations (more specifically: If an n-bit string is considered to occupy one memory cell and the union of two of them computable within one step), the above data structure including for each cell its visibility V(S, C, S) uses storage O(n 4 ) and can be calculated in time O(n 4 · log 2 n). d) Item a) extends to the case of (d − 1)-simplices in d-dimensional space in that the number of convex cells with equivalent observer visibility can be bounded by O(n) d 2 .
Proof. a) Draw lines through all 2n 2 pairs of the 2n segment endpoints. It is easy to see that, in order for a near segment to appear in sight, the observer has to cross one of these O(n 2 ) lines; compare Lemma 15 below. Hence, within each of the O(n 4 ) cells they induce, the subset of segments weakly visible remains the same; compare Figure 1 determining the visibility count of each cell were two separate steps which we now merge using divide-and-conquer: In the first phase calculate the VSP of the first two segments of S, then that of the next, and so on; in each VSP store, for each cell, the visibility vector, i.e. the 0/1 bitstring recording which segments from S are visible (1) and which are not (0). In the next phase overlay the first two VSPs of two segments into one of the first four segments, and store for each refined cell the union of the 0/1 bitstrings: thus keeping track of its visibility; similarly for the next two VSPs of the next four segments. Then proceed to VSPs of eight segments each; and so on. We therefore have O(log n) phases; and, according to [BKOS97, Theorem 2.6], the last (as well as each previous) phase takes time O(n 4 · log n).

Size of Visibility Space Partitions
Lemma 9a+b) bounds the size of the VSP data structure by order n 4 . It turns out that this bound is sharp in the worst case-but not for many 'realistic' examples. This is due to many of the Θ(n 2 ) lines employed in the proof of Lemma 9a) inducing unnecessarily fine subdivisions of viewpoint space. In Figure 3a) for instance, the dotted parts are dispensible. In order to avoid trivialities, we want to restrict to nondegenerate segment configurations S. However this notion is subtle because the lines induced by S defining the VSP typically are degenerate: many (more than two) of them meet in one common (segment end) point.

Definition 10. A family S of segments in the plane is nondegenerate if i) any two segments meet only in their common endpoints. ii) No three endpoints share a common line; iii) Any two lines, defined by pairs of endpoints, do meet.
We have already referred to (and implicitly employed in Lemma 9 a refinement of) the Visibility Space Partition; so here finally comes the formal Definition 11. For two non-degenerate collections S and T of segments in the plane, partition all viewpoints p ∈ R 2 into classes having equal visibility V(S, p, T ). Moreover let VSP(S, T ) denote the collection of connected components of these equivalence classes. The size of VSP is the number of line segments forming the boundaries of these components. Since the Visibility Graph itself can have at most quadratically more edges than vertices, Item c) strengthens Lemma 9a). Empirically we have found that a 'random' scene typically induces a VSP of roughly quadratic size. This agrees with a 'typical' scene to have a linear size Visibility Graph according to [ELPZ07].

Proof (Lemma 12).
a) Figure 2 is a small modification of [ORou87, Fig. 8.13]. The long bottom line segment T is visible from the upper half iff the observer can peep through two successive gaps simultaneously, i.e. from any position on the Θ(n 2 ) stripes but not from the ellipses. When moving from an ellipse to another, T flashes into sight and is then hidden again. There are Θ(n 4 ) such ellipses.
It is easy to see that this example is combinatorially stable under small perturbation and hence can be made non-degenerate. b) Consider Figure 4: Within each cell C of the segment arrangement, all segments are always visible; hence C is also a cell of the VSP. And the exterior of S gives rise to another 9 VSP cells. c) Recall the proof of Lemma 9a); but throw in the observation that crossing the line L a, b induced by two endpoints a and b (say, of segments S 1 , S 2 ∈ S, respectively) does not induce a change in visibility if a and b are occluded from each other by some further segment S ∈ S: compare

Output-Sensitive VSP Calculation
In view of the large variation of VSP sizes from order n to order n 4 according to Lemma 12, the algorithms indicated in Lemma 9b+c) for their calculation are reasonable only in case of large VSPs. We now present an output-sensitive improvement of Lemma 12d):  Theorem 13. In 2D, the data structure of Lemma 9a-c) can be computed in time O(n 2 · log n + N · log n) in the sense of (the computational model referred to in) Lemma 9c), where N denotes the combinatorial complexity of VSP(S, S).
Proof. We start as in the proof Lemma 9 with the order n 2 lines induced by all pairs of segment endpoints. Now the idea is to extend Lemma 12c), namely to take into consideration only those parts the lines lines are cut into, which to cross actually changes the visibility. Indeed, these sub-lines constitute the boundaries of the cells of the VSP and therefore determine its complexity.
i) Take such a line L a, b passing through segment endpoints a and b of segments S 1 and S 2 ∈ S. To an observer crossing L a, b , the visibility can, but need not, change-and we want to determine if and where it does. First observe that the middle part ( a, b) of L a, b can be disposed off right away (unless a and b are endpoints of the same segment, but these O(n) cases give rise to only O(n 2 ) combinatorial complexity anyway) because crossing it never changes the visibility; compare Figure 3. Now consider the two remaining unbounded rays of L a, b , L a starting from a and L b starting from b. If, say, L a intersects some other segment S ∈ S in some point c, then traversing the part of L a beyond that point does not affect the visibility either, as S 2 is 'shielded' from sight by S anyway; again cf. Figure 3. So let L ′ a := ( a, c) in this case, L ′ a := L a otherwise; and similarly for L ′ b . Now crossing L ′ b at some point may or may not alter the visibility of (at least one of) S 1 , S 2 , S (the latter being a segment 'opposite' to b along L a, b ) but if it does so, then it does so at every point of L ′ b . Hence we will either keep the whole L ′ b , or drop it entirely; similarly for L ′ a . ii) Now since those two alternatives-namely keeping or dropping L ′ b -depend only on S 1 , S 2 , S, they can be distinguished in constant time. Moreover, after O(n 2 ) preprocessing time and space for S, each L a, b can be decomposed into the two parts L ′ a and L ′ b as the result of a ray shooting query among S in logarithmic time; see e.g. [Pocc90, Theorem 3.2]. The line parts L ′ kept will in general intersect each other. So next cut them into nonintersecting maximal sub-segments. By the above observations, these constitute the boundaries of the VSP. And as a standard segment intersection problem, they can be determined in time O(n 2 · log n + N ); cf. e.g. [BKOS97, Section 2.5].
The resulting (sub-)segments give rise to a planar subdivision. For instance they cannot contain leaf (e.g. degree-1) vertices: circling around such a vertex one way would change the visibility and the other way would not. Therefore the data structure admitting logarithmic-time pointlocation in the VSP can be calculated in space O(N ) and time O(N · log n), recall [BKOS97, Theorem 6.8].
iii) Determining the visibilities as in the proof of Lemma 9b) yields a factor n overhead; and the divide-and-conquer approach of Lemma 9c) seems inapplicable because of the correlations between segments in Step ii), namely cutting off L a, b induced by S 1 , S 2 at the first further segment S hit. On the other hand, each L ′ a (and similarly for L ′ b ) by construction induces a definite change in visibility when crossed: we may presume this information to have been stored with L ′ a at the beginning of Step ii). Hence we may start at one arbitrary cell of the arrangement, calculate its visibility according to Lemma 7, and then traverse the rest of the arrangement cell by cell while keeping track of the visibility changes induced by (and stored with) each cell boundary. Such a trade-off result from time to space has become famous in the general context of structural complexity [HPV77]. Note that, obeying sublinear time, we can get arbitrarily close to cubic space-yet remain far from the joint resources consumption of an interval tree (Section 2.1). But first comes the already announced Corollary 27, the main result of this section, presents a randomized approximation within sublinear time using almost cubic space in the worst-case and almost linear space in the 'typical' one.

Deterministic Approach: Relaxed VSPs
Visibility space partitions, and the algorithms based upon them, are so memory expensive because they discriminate (i.e. introduces separate arrangement cells for) observer positions whose visibility differs by as little as one; recall Definition 11. It seems that considerably more (time and) space efficient algorithms may be feasible by partitioning observer space into (or merely covering it by) more coarse classes: Definition 18. Fix k ∈ N and collections S and T of non-intersecting segments in the plane. Some covering {C 1 , . . . , C I } of R 2 is called a k-relaxed VSP of (S, T ) if In the sequel we shall restrict to k-relaxed VSPs which constitute planar subdivisions (i.e. each C i being a simple polygon); and refer to their size in the sense of Definition 11.
Indeed, such VSPs allow for locating a given observer position x in logarithmic time to yield a cell C i ∋ x which, during preprocessing, had been assigned a value V(S, q, T ) approximating V(S, x, T ) up to absolute error at most k.
Example 19. For Card T ≤ k, the trivial planar subdivision {R 2 } is a k-relaxed VSP of (S, T ).
In particular the quartic lower size bound of Lemma 12b) applies only to 0-relaxed VSPs but breaks down for k ≥ 1.
This example suggests that much smaller (e.g. worst-case quadratic) sizes might become feasible when considering k-relaxed VSPs for, say, k ≈ √ n or even k ≈ n/ log n. Indeed we have the following lower and upper bounds: Proposition 20. a) For each n, k there exists a non-degenerate family S of segments in the plane such that any k-relaxed VSP has size at least n · ⌊(n − 1)/(k + 1)⌋. b) There also exist such families such that any k-relaxed VSP has size at least Ω(n 4 /k 4 ). Recall that N ≤ m 2 ≤ n 4 , thus leaving quadratic gap between a) and d) for k small; and between b) and d) for k large. Item c) succeeds over d) in cases where N asymptotically does not exceed m 2 /k. Figure 6 with n = 13 segments which obviously generalizes to arbitrary n.

Proof. a) Consider
Moving from segment a along the arrow, each time crossing a dashed line amounts to an increase in visibility from {a} via {a, b}, {a, b, c} and so on up to entire S. Hence to obtain cells of viewpoints with visibility varying by at most k, we must keep at least every (k + 1)-st dashed border, that is ⌊(n − 1)/(k + 1)⌋ out of n − 1. By symmetry, the same argument applies when moving from segment b along the arrow, or from any other segment. b) A closer look at Figure 6 reveals it to induce a VSP of size Ω(n 4 ): For any segment, there are linearly many separate cones from which it can be seen through the gaps between the other segments; hence we have quadratically many cones, of which almost any two intersect; compare Figure 7, particularly its right part. Now in order to argue about k-relaxed VSPs, replace in Figure 6 each single segment by k scaled and shifted copies as indicated in the left of Figure 7; that is we now have a scene of size N = n · k. Observe that, when entering and passing through a cone of visibility, the number of segments visible increases from its original value to an additional k (drawn in levels of gray). The visibility number thus varies by k + 1, requiring a k-relaxed VSP to subdivide the cone; indeed the entire cone! By the above considerations, these necessary boundaries induce an arrangement of complexity Ω(n 4 ) which, expressed in the size N of the scene, is Ω(N 4 /k 4 ) as claimed. c) Classify the cells of VSP(S, S) according to their visibility count; and let N i denote the number of boundary segments of VSP(S, S) separating a cell with visibility count i from one with visibility count i + 1. Since any boundary segment does so for some i = 1, . . . , n − 1, N = N 1 + N 2 + · · · + N n−1 = (N 1 + N k+2 + N 2(k+1)+1 + . . .) + (N 2 + N k+3 + N 2(k+1)+2 + . . .) Hence by pigeonhole principle there exists 1 ≤ κ ≤ k + 1 such that ⌊N/(k + 1)⌋ ≥ N κ + N k+1+κ + N 2(k+1)+κ + . . . Now keep from VSP(S, S) exactly those boundary segments that either separate cells with visibility count κ from ones with visibility count κ + 1, or cells with visibility count k + 1 + κ from ones with visibility count k + 2 + κ, or cells with visibility count 2(k + 1) + κ from visibility count 2(k + 1) + κ + 1 and so on. By the above considerations, this planar subdivision has complexity at most ⌊N/(k + 1)⌋. And by construction, it joins cells having visibility counts j · (k + 1) + κ + 1, j · (k + 1) + κ + 2, j · (k + 1) + κ + 3, . . . , j · (k + 1) + (k + 1) + κ; but maintains their separation from cells with visibility count (j + 1) · (k + 1) + κ + 1, because those boundary segments are precisely the ones deliberately kept. Hence the joined coarsened (i.e. super-) cells indeed contain only viewpoints with visibility count differing by at most k. We remark that Item c) considers a certain sub-arrangement of the 0-relaxed VSP, whereas the planar subdivision due to Item d) uses cell boundaries not necessarily belonging to the VSP. Also, the size O(r d ) of the cuttings employed in Items d) and e) is known to be optimal in general; but this optimality does not necessarily carry over to our application in visibility, recall the gaps between lower and upper bounds in Items a) to d). Substituting k = δ · n yields Corollary 21. For each collection S of non-degenerate segments in the plane and k ∈ N, there exists a data structure of size O min{N/(δ · n), m 2 /(δ · n) 2 } that allows to approximate, given x ∈ R 2 , the visibility ratio V(S, x, S)/ Card(S) up to absolute error δ > 0 in time O(log n).
Notice that we only claim the existence of such small data structures. In order to construct them, the proofs of Proposition 20c) and d) both proceed by first calculating the 0-relaxed VSP and then coarsening it. Specifically for Proposition 20d), a Triangular Cutting can be obtained in time O(m · r · polylog) [Agar90]; but determining the visibility count for each triangle ∆ i costs O(n · log n) according to Lemma 8; or can be taken from the 0-relaxed VSP. The preprocessing time for Proposition 20c+d) thus is, up to polylogarithmic factors, that of Theorem 13, i.e. roughly O(N ): independent of, and not taking advantage of large values of, k. For the configuration from Lemma 12a) for instance (recall Figure 2), this results in a preprocessing time of order n 4 although the resulting 1-relaxed VSP has only size O(n 2 ). Alternatively, apply Lemma 8 to (one point from) each triangle ∆ i to obtain a running time of roughly output×n, that is still off optimal by one order of magnitude. And finally, the asymptotically 'small' size and time for calculating triangular cuttings hide in the big-Oh notation some large constants which are believed to prevent practical applicability.

Random Sampling
Both size and query time of the data structure due to Corollary 21 are rather low; but because of the infavourable preprocessing time and hidden big-Oh overhead indicated above, we now proceed to random sampling, based on a rather simple generic algorithm: Item iv) is justified by the following Lemma 23. Fix x ∈ R d and δ > 0, then choose T ⊆ S as m independent identically distributed random draws from S. It holds In other words: In Algorithm 22 taking m (quadratic in the aimed absolute accuracy δ but) constant with respect to the scene size n suffices to achieve the desired approximation with constant probability; slightly increasing it further amplifies exponentially the chance for success.
Remark 24. a) It is easy to see that a fixed relative accuracy can be attained, for V(S, x, S)/n → 0, only by samples of size m → n: If only one segment is visible, it must get sampled to be detected. b) Also the visibility of the sample is crucially to be considered with respect to the entire scene, i.e. V(S, x, T ) rather than V(T , x, T ).

Proof (Lemma 23).
It is well-known [MoRa95,AlSp00] that a sum X := m i=1 X i of independent {0, 1} trials X 1 , . . . , X m satisfies the Chernoff-Hoeffding Bound Prob |X/m − µ| ≥ δ ≤ 2 · exp(−2m · δ 2 ) where µ denotes the expectation of X i . In our case, let X i denote the event that the i-th draw S i ∈ S is visible from x through S. This happens with probability µ = V(S, x, S)/n, hence X = V(S, x, T ).

The VC-Dimension of Visibility
Note that the random experiment T and the probability analysis of its properties in Lemma 23 holds for each x but not uniformly in x. This means for our purpose to re-sample T ⊆ S at every frame. On the other hand, the above considerations have not exploited any geometry. An important connection between combinatorial sampling and geometric properties is captured by the Vapnik-Chervonenkis Dimension [AlSp00]: Fact 25. Let X be a set and R a collection of subsets R ⊆ X. Denote by the VC-Dimension of (X, R).
Then with probability at least 1 − p, it holds for each R ∈ R: Then with probability at least 1 − p it holds for each R ∈ R: Card b) A random subset T ⊆ S of cardinality m ≥ Ω d 2 · log(n) · log(d · log n/δ)/δ satisfies with constant (and easily amplifiable) probability that, whenever at least a δ-fraction of the simplices of S are visible from x ∈ R d through S, then so is some simplex of T . c) A random subset T ⊆ S of cardinality m ≥ Ω d 2 · log(n) · log(d · log n/δ)/δ 2 satisfies with constant (yet easily amplifiable) probability that V(S, x, T )/ Card(T ) deviates from V(S, x, S)/ Card(S) absolutely by no more than δ. d) The bound obtained in a) is asymptotically optimal with respect to n: In R 2 there exist nondegenerate collections S = X of n line segments such that VCdim(X, R) ≥ log n− O(loglog n).
Proof. a) Lemma 9d) implies Card R ≤ O(n) d 2 . Hence, in Equation (1), 2 Y = {Y ∩ R : R ∈ R} requires 2 Card Y ≤ Card R and therefore Card Y ≤ d 2 · log n + O(1) . b) and c) follow by plugging Item a) into Fact 25b+c). d) Figure 8 below obviously extends to the construction of k segments of which, using 2 k · k/2 additional segments as 'shields', each subset appears as a visible set V(S, x, S) for some x.
That is a scene S of size n = k + 2 k · k/2 containing a subset Y of size k = log n − O(loglog n) as in Equation (1). ⊓ ⊔ Fig. 8. 3 segments of which, shielded by 12 further segments, each of its 8 subsets appears as visible set.

Main Result
Lemma 26c) enhances Lemma 23: The latter is concerned with the probability of a constant -size sample T to be representative (i.e. to approximate the visibility ratio) with respect to a fixed viewpoint-i.e. our application would (have to) re-sample in each frame! The former lemma on the other hand asserts that a polylogarithmic-size sample, drawn once and for all, be suitable with respect to all viewpoints! In particular we may preprocess the visibility of each T ∈ T separately according to Theorem 14 and obtain, employing Scholium 16: Corollary 27. Given 0 < δ < 1, a collection S of n non-crossing segments in the plane (d = 2), and 1 ≤ ℓ ≤ n ≤ m where m denotes the size of the Visibility Graph of S. Then a randomized algorithm can preprocess S within time O n · log n + m 2 · polylog n · log 1 δ /(ℓ · δ 2 ) and space O m 2 · polylog n · log 1 δ /(ℓ · δ 2 ) into a data structure having with high probability the following property: Given x ∈ R 2 , one can approximate the visibility ratio V(S, x, S)/ Card(S) up to absolute error at most δ in time O ℓ · polylog n · log 1 δ /δ 2 .
Again, note the trade-off between space and query time gauged by the parameter ℓ. And, remembering the paragraph following Lemma 12, m is 'typically' linear in n; hence choosing ℓ = n 1−ǫ , the space can be made arbitrarily close to linear while maintaining sublinear query time, thus complying with Paradigm 4!

Empirical Evaluation
The present section demonstrates the practical applicability of the algorithm underlying Corollary 27: It is (not trivial but neither) too hard to implement, constants hidden in big-Oh notation are modest, and query time can indeed be traded for memory. Measurements were obtained on an Intel R Dual TM 2 CPU 6700 running at 2.66GHz under openSUSE 11.0 equipped with 4GB of RAM. The implementation is written in Java version 6 update 11. Calculations on coordinates use exact rational arithmetic based on BigIntegers.

Benchmark Scenes
We consider three kinds of 'virtual scenes' in 2D, that is collections of non-intersecting line segments, compare Figure 9: A) Sparse scenes representing forest-like virtual environments with long-range visibility; As indicated by the above classification, these scenes contain some regularity. More precisely, their respective visibility ratios obey qualitative deterministic laws, see Figure 10a). On the other hand these scenes are constructed using some random process, which means instances can be made up of any desired size n.
Specifically all scenes arise from throwing into each square of an √ n × √ n grid one randomly oriented segment. For Scene A, these segments are then shrunk by a factor ∼ = √ n to yield an average visibility count proportional to n, see Figure 10a). For Scene B, each segment sequentially is grown as to just touch some other one: remember we want to comply with Definition 10; as expected (and corresponding to Lemma 12b) this results in constant visibility counts. Scene C finally arises from Scene B by shrinking the segments again; here the visibility count grows roughly proportional to n 0.3 .  Fig. 10. a) Maximum/average/minimum visibility counts for Scenes A to C. b) Variance of the output of the randomized algorithm. Figure 10b) indicates the quality of approximation attained by Corollary 27: Recall that the preprocessing step randomly selects k elements of the scene as targets; and the proof shows that asymptotically this sample is 'representative' for the entire scene with high probability. Our implementation chose k = 10 · log 2 (n) which turned out to yield a practically good approximation indeed. More precisely, Figure 10b) displays the 1σ confidence interval estimates for scenes A) and C) from various viewpoints, normalized to (i.e. after subtracting the) mean 0.

Memory Consumption versus Query Time
Preprocessing space and query time are two major resource contraints for many applications such as the one we aim at. We have thus performed extensive measurements of these quantities for the scene types A) to C) mentioned above. It turns out that for A) our data structure takes roughly linear space and for B) roughly quadratic one, whereas for C) it grows strictly stronger; see Figure 11a). Here we refer to the setting ℓ = 1. For scene C) we have additionally employed the trade-off featured by Corollary 27 to reduce the memory consumption at the expense of query time; specifically, scene E) means scene C) with ℓ := n 1/4 , and scene D) refers to ℓ := n 1/2 . It turns out that the latter effectively reduces the size to quadratic, see Figure 11a). On the other hand, the saved memory is paid for by an increase in query time; cf. Figure 11b). Indeed at scenes of size n ≈ 20, 000 each query is estimated to take about 50ms, that is as long as one frame may last at an interactive rate of 20fps. Whereas scene E), that is scene C) with ℓ = n 1/4 instead of ℓ = n 1/2 , is estimated to still remain far below this limit for much, much larger scenes n; not to mention scenes A) to C), i.e. with ℓ = 1.

Conclusion
Our benchmarks range up to n ≈ 8, 000 when the data structure hit an overall memory limit of 16GB. This may first seem to fall far short of the original sizes aimed at in Section 1.1. On the other hand, -the measurements obtained turn out to depend smoothly on n and thus give a sufficient indication of, and permit to extrapolate with convincing significance, the behavior on larger scenes. -By proceeding from single geometric simplicies to entire 'virtual objects' (like e.g. a house or a car) as rendering primitives, one can in practice easily save a factor of 100 or 1000. -Temporal and spacial coherence of an observer moving within a virtual scene suggests that visibility counting queries need not be performed in each frame separately. Moreover our CPUbased algorithm can be run concurrently to the graphics processing unit (GPU). These two improvements in running time can then be traded for an additional saving in memory.
-In order to attain and access the 16GB mentioned above, we employed secondary storage (a harddisk): with an unfavorable increase in preprocessing time but suprisingly little effects on the query time.
These observations suggest that our algorithm's practicality can be extended to n much larger than the above 8, 000; yet doing so is beyond the purpose of the present work. It is thus fair to claim as main benefit of our contribution in Corollary 27 an (as opposed to Corollary 21) practically relevant approach to approximate visibility counting based on the ability to trade (otherwise prohibitive quartic) preprocessing space for (otherwise almost neglectible logarithmic) query time.
5 Perspectives a) We have treated the observer's position x as an input newly given from scratch for each frame.
In practice however p is more likely to move continuously and with bounded velocity through the scene. This should be exploited algorithmically, e.g. in form of a visibility count maintenance problem [Pocc90, Section 3.2]. b) How does Theorem 14 extend from 2D to 3D, what is the typical size of a 3D VSP? c) The quartic worst-case size of 2D VSPs (and quadratic typical yet even of order n 9 for 3D) arises from visibility considered with respect to perspective projections; whereas for orthographic projections, it drops to O(n 2 ) (in 2D; in 3D: order n 6 ) [Schi01]. d) The counterexamples in Lemma 12a) and Lemma 26d) and also Proposition 20a) employ (after scaling the entire scene to unit size) very short and/or very close segments. We wonder if such worst cases can be avoided in the bit cost model, i.e. with respect to n denoting the total binary length of the scene description on an integer grid.

Remarks on Lower Bounds
We have presented various data structures and algorithms for visibility counting, trading preprocessing space for query time. It would be most interesting to complement these results by corresponding lower bounds of the form: preprocessing space s requires, in some appropriate model of computation, query time at least Ω f (s) . Unfortunately techniques for Friedman's Arithmetic Model, which have proven so very successful for range query problems [Chaz90], do not apply to the non-faithful semigroup weights of geometric counting problems, not to mention decision Problem 5; and approximate, rather than exact, counting makes proofs even more complicated.
On the other hand, we do have some lower bounds: namely on the sizes of VSPs and relaxed VSPs in Lemma 12a) and Proposition 20a+b). These immediately translate to lower bounds on the sizes of Linear Branching Programs, based on the observation that any such program needs a different leaf for each different convex cell of inputs leading to the same output value, compare [DFZ02].
But then again this seemingly natural model of computation is put into question when considering the algorithms from Sections 2.1 and 2.2: Both have, in spite of Lemma 12a), merely (weakly) linear size. Superficially, Lemma 8 seems to employ transcendental functions for angle calculations; but these can be avoided by comparing slopes instead of angles-however employing divisions. These, again, can be replaced: yet multiplications do remain and make the algorithm inherently nonlinear a branching program.

Visibility in Dimensions > 2
We had deliberately restricted to the planar case of line segments. Many virtual scenes in interactive walkthrough applications can be described as 2 1 2 -dimensional: buildings of various heights yet rooted on a common plane.
But how about the full 3D case? Here we observe a quadratic 'almost' lower bound on the joint running time of preprocessing and querying for the 3D counterpart to Problem 5. To this end recall the following famous Problem 28 (3SUM). Given an n-element subset S or R, do there exist a, b, c ∈ S such that a + b + c = 0 ?
It admits an easy algebraic O(n 2 )-time algorithm but is not known solvable in subquadratic time. Similar to Boolean Satisfiability (SAT) and the theory of N P-completeness, 3SUM has led to a rich family of problems mutually reducible one to another in softly linear time O(n · polylog n) and hence called 3SUM-complete; for example it holds [GaOv95, Section 6.1]: Fact 29. Given a collection S of opaque horizontal triangles in space, one further horizontal triangle T , and a viewpoint p ∈ R 3 . The question of whether some point of T is visible from p through S (called Visible-Triangle) is 3SUM-complete.
In particular there is no 3D counterpart to the Interval Tree solving the corresponding 2D problem in time O(n · log n), recall Section 2.1.