On k-sets in arrangements of curves and surfaces
The article considers simple curves in two dimensions each of which separates the plane into two connected components, the interior and the exterior of the curve. Given a set \(S\) of such curves, the \(k\)-set of \(S\) is defined as the set of those intersection points which are covered by \(k\) interiors. The \(\leq k\)-set is defined analogously. Various bounds on the size of \(\leq k\)-sets are given, for example \({\mathcal O}(nk)\) if any two curves intersect at most twice, \(\Theta(nk\alpha(n/k))\) (\(\alpha\) is the inverse of the Ackermann-function) if they intersect at most three times, and \(\Theta(k^ 2\lambda_ s(n/k))\) if they are \(x\)-monotone and intersect at most \(s\) times. These results are obtained by applying a probabilistic technique of Clarkson and Shor to relate the size of \((\leq k)\)-sets to the size of 0-sets of a sample of the curves. Several applications of these results are given including efficient data structures for disc-stabbing, i.e. reporting from a set of discs in the plane all those that contain a given query point, with generalizations to half-planes (bounded by curves) and arbitrary disjoint convex sets.
- Combinatorial configurations, quasiline arrangements, and systems of curves on surfaces
- Arrangements of curves and algebraic surfaces
- scientific article; zbMATH DE number 4060713
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- On `\(k\)-sets' in the plane
- On algebraic surfaces associated with line arrangements
- scientific article; zbMATH DE number 1467259
- scientific article; zbMATH DE number 2123617
- On a class of algebraic surfaces constructed from arrangements of lines
- On several Kummer surfaces
- Applications of random sampling in computational geometry. II
- Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
- Fractional cascading. II: Applications
- Geometric permutations for convex sets
- Halfspace range search: An algorithmic application of k-sets
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 4060713 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- Lower Bounds on the Complexity of Polytope Range Searching
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- On a circle placement problem
- On arrangements of Jordan arcs with three intersections per pair
- On the number of k-subsets of a set of n points in the plane
- On the two-dimensional Davenport-Schinzel problem
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
- Power Diagrams: Properties, Algorithms and Applications
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Some dynamic computational geometry problems
- The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
- The number of small semispaces of a finite set of points in the plane
- The power of geometric duality
- The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
- The upper envelope of piecewise linear functions: Algorithms and applications
- Upper bounds on geometric permutations for convex sets
- Coloring geometric range spaces
- Intersection queries in sets of disks
- Arrangements of oriented hyperplanes
- \(k\)-sets and random hulls
- Computing the smallest k-enclosing circle and related problems
- New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
- Almost tight upper bounds for lower envelopes in higher dimensions
- 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
- On fat partitioning, fat covering and the union size of polygons
- Kinetic \(k\)-semi-Yao graph and its applications
- Almost tight upper bounds for the single cell and zone problems in the three dimensions
- The overlay of lower envelopes and its applications
- Lines in space: Combinatorics and algorithms
- Algorithmic aspects of proportional symbol maps
- On the arrangement of stochastic lines in \(\mathbb{R}^2\)
- Translating a convex polygon to contain a maximum number of points.
- Detecting commuting patterns by clustering subtrajectories
- Maximizing the area of overlap of two unions of disks under rigid motion
- On s -intersecting curves and related problems
- SMALLEST COLOR-SPANNING OBJECT REVISITED
- Near-optimal lower bounds for -nets for half-spaces and low complexity set systems
- Approximate $k$-Nearest Neighbor Graph on Moving Points
- On intersection searching problems involving curved objects
- Filling polyhedral molds
- Computing the smallest k-enclosing circle and related problems
- Decomposition of Multiple Packings with Subquadratic Union Complexity
- Point enclosure problem for homothetic polygons
- Arrangements on parametric surfaces. I: General framework and infrastructure
- Point enclosure problem for homothetic polygons
- More dynamic data structures for geometric set cover with sublinear update time
- Sunflowers in set systems of bounded dimension
- Covering many or few points with unit disks
This page was built for publication: On \(k\)-sets in arrangements of curves and surfaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1179129)
