On \(k\)-sets in arrangements of curves and surfaces

DOI10.1007/BF02574706zbMath0744.68132OpenAlexW4242657188MaRDI QIDQ1179129

Micha Sharir

Publication date: 26 June 1992

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131175

zbMATH Keywords

combinatorial geometry\(k\)-setsDavenport-Schinzel-sequences

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete geometry (52C99)

Related Items

Computing the smallest \(k\)-enclosing circle and related problems, On the arrangement of stochastic lines in \(\mathbb{R}^2\), Kinetic \(k\)-semi-Yao graph and its applications, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Almost tight upper bounds for lower envelopes in higher dimensions, Covering many or few points with unit disks, On intersection searching problems involving curved objects, Filling polyhedral molds, Computing the smallest k-enclosing circle and related problems, Almost tight upper bounds for the single cell and zone problems in the three dimensions, The overlay of lower envelopes and its applications, 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects, Lines in space: Combinatorics and algorithms, On fat partitioning, fat covering and the union size of polygons, Point enclosure problem for homothetic polygons, Approximate $k$-Nearest Neighbor Graph on Moving Points, Decomposition of Multiple Packings with Subquadratic Union Complexity, Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems, Algorithmic aspects of proportional symbol maps, Intersection queries in sets of disks, Translating a convex polygon to contain a maximum number of points., Coloring geometric range spaces, DETECTING COMMUTING PATTERNS BY CLUSTERING SUBTRAJECTORIES, SMALLEST COLOR-SPANNING OBJECT REVISITED, MAXIMIZING THE AREA OF OVERLAP OF TWO UNIONS OF DISKS UNDER RIGID MOTION, Arrangements of oriented hyperplanes, \(k\)-sets and random hulls

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper bounds on geometric permutations for convex sets
• The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
• The upper envelope of piecewise linear functions: Algorithms and applications
• On the number of k-subsets of a set of n points in the plane
• On a circle placement problem
• The number of small semispaces of a finite set of points in the plane
• Some dynamic computational geometry problems
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Halfspace range search: An algorithmic application of k-sets
• The power of geometric duality
• Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• Fractional cascading. II: Applications
• Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
• On arrangements of Jordan arcs with three intersections per pair
• Applications of random sampling in computational geometry. II
• Geometric permutations for convex sets
• On the two-dimensional Davenport-Schinzel problem
• Lower Bounds on the Complexity of Polytope Range Searching
• Power Diagrams: Properties, Algorithms and Applications