scientific article; zbMATH DE number 732977

Publication date: 12 March 1995

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

computational geometry formal languages Davenport-Schinzel sequences

Combinatorics on words (68R15) Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items (only showing first 100 items - show all)

2-point site Voronoi diagrams ⋮ Shattering a set of objects in 2D ⋮ On the minimum-area rectangular and square annulus problem ⋮ Kinetic \(k\)-semi-Yao graph and its applications ⋮ An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments ⋮ An optimal \(O(n\log n)\) algorithm for finding an enclosing planar rectilinear annulus of minimum width ⋮ On the dilation spectrum of paths, cycles, and trees ⋮ Kinetic collision detection with fast flight plan changes ⋮ Farthest line segment Voronoi diagrams ⋮ Excess in arrangements of segments ⋮ Combinatorial aspects of Davenport-Schinzel sequences ⋮ A crossing lemma for Jordan curves ⋮ From proximity to utility: a Voronoi partition of Pareto optima ⋮ Kinetic and dynamic data structures for convex hulls and upper envelopes ⋮ A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams ⋮ The common exterior of convex polygons in the plane ⋮ 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects ⋮ The maximin line problem with regional demand ⋮ Parametric multiple sequence alignment and phylogeny construction ⋮ An improved bound on the number of unit area triangles ⋮ Revisiting \(k\)-sum optimization ⋮ On trees and noncrossing partitions ⋮ Indexing moving points ⋮ Bounding sequence extremal functions with formations ⋮ Bounds on parameters of minimally nonlinear patterns ⋮ Querying two boundary points for shortest paths in a polygonal domain ⋮ Covering moving points with anchored disks ⋮ On the union of cylinders in three dimensions ⋮ Forest-like abstract Voronoi diagrams in linear time ⋮ Separating bichromatic point sets by L-shapes ⋮ A kinetic triangulation scheme for moving points in the plane ⋮ Farthest-polygon Voronoi diagrams ⋮ The overlay of minimization diagrams in a randomized incremental construction ⋮ Continuous location of dimensional structures. ⋮ Coverage restricted to an angle ⋮ Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions ⋮ Stable Delaunay graphs ⋮ On the computation of zone and double zone diagrams ⋮ Remarks on the computation of the horizon of a digital terrain ⋮ Computing a minimum-width square annulus in arbitrary orientation ⋮ Improved complexity results for the robust mean absolute deviation problem on networks with linear vertex weights ⋮ Computing an obnoxious anchored segment. ⋮ Tight bounds on the maximum size of a set of permutations with bounded VC-dimension ⋮ Lines avoiding balls in three dimensions revisited ⋮ On levels in arrangements of surfaces in three dimensions ⋮ The weighted farthest color Voronoi diagram on trees and graphs. ⋮ Spanning trees crossing few barriers ⋮ Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences ⋮ Computing the nearest polynomial with a zero in a given domain by using piecewise rational functions ⋮ Sorting weighted distances with applications to objective function evaluations in single facility location problems. ⋮ On the number of views of translates of a cube and related problems. ⋮ Kinetic collision detection between two simple polygons. ⋮ Union of random Minkowski sums and network vulnerability analysis ⋮ Covering point sets with two disjoint disks or squares ⋮ On the performance of the ICP algorithm ⋮ Disjoint edges in topological graphs and the tangled-thrackle conjecture ⋮ Improved bounds on the union complexity of fat objects ⋮ On the number of maximum empty boxes amidst \(n\) points ⋮ The combinatorial encoding of disjoint convex sets in the plane ⋮ Minimum width color spanning annulus ⋮ Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices ⋮ Data imprecision under \(\lambda\)-geometry model ⋮ Distribution-sensitive construction of the greedy spanner ⋮ \(L^3\) estimates for an algebraic variable coefficient Wolff circular maximal function ⋮ Kinetic spanners in \(\mathbb R^{d}\) ⋮ On the structure of the solution set for the single facility location problem with average distances ⋮ Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts ⋮ Minimum vertex cover in rectangle graphs ⋮ On the computation of an arrangement of quadrics in 3D ⋮ Polygonal chain approximation: A query based approach ⋮ Multi-dimensional dynamic facility location and fast computation at query points ⋮ Ray shooting and stone throwing with near-linear storage ⋮ Computing pseudotriangulations via branched coverings ⋮ Fréchet distance between a line and avatar point set ⋮ Two proofs for shallow packings ⋮ High girth augmented trees are huge ⋮ Polynomial-time approximation algorithms for anchor-free TDoA localization ⋮ On overlays and minimization diagrams ⋮ Strongly polynomial-time truthful mechanisms in one shot ⋮ On regular vertices of the union of planar convex objects ⋮ An algorithmic toolbox for network calculus ⋮ A near-linear algorithm for the planar segment-center problem ⋮ The union of moving polygonal pseudodiscs -- combinatorial bounds and applications ⋮ Improved algorithms for the multicut and multiflow problems in rooted trees ⋮ Single facility collection depots location problem in the plane ⋮ Notes on the complexity of exact view graph algorithms for piecewise smooth algebraic surfaces ⋮ Kinetic maintenance of mobile \(k\)-centres on trees ⋮ Conflict-free coloring of unit disks ⋮ Kinetic hanger ⋮ Ready, set, go! The Voronoi diagram of moving points that start from a line ⋮ Separable partitions ⋮ Searching for equilibrium positions in a game of political competition with restrictions ⋮ Facility location problems in the plane based on reverse nearest neighbor queries ⋮ Solving restricted line location problems via a dual interpretation ⋮ Extremal problems on triangle areas in two and three dimensions ⋮ Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation ⋮ Extremal problems for colored trees and Davenport-Schinzel sequences ⋮ On numbers of Davenport-Schinzel sequences ⋮ The higher-order Voronoi diagram of line segments ⋮ Stability versus speed in a computable algebraic model

This page was built for publication: