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

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, OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS, Robust mean absolute deviation problems on networks with linear vertex weights, Deletion in abstract Voronoi diagrams in expected linear time and related problems, Space-aware reconfiguration, Kinetic Geodesic Voronoi Diagrams in a Simple Polygon, Parametric matroid interdiction, Throwing a sofa through the window, The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs, Faster algorithms for largest empty rectangles and boxes, On the Richter–Thomassen Conjecture about Pairwise Intersecting Closed Curves, Unnamed Item, Linear approximation of simple objects, On the zone of a circle in an arrangement of lines, On the zone of a circle in an arrangement of lines, A MONOTONIC CONVOLUTION FOR MINKOWSKI SUMS, CONTINUOUS PATH VERIFICATION IN MULTI-AXIS NC-MACHINING, Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications, Optimal Triangulation with Steiner Points, MAXIMIZING A VORONOI REGION: THE CONVEX CASE, A simple and efficient kinetic spanner, Separating objects in the plane by wedges and strips, The $k$-centrum multi-facility location problem, On the number of regular vertices of the union of Jordan regions, An efficient algorithm for the three-dimensional diameter problem, Polygon decomposition for efficient construction of Minkowski sums, Guarding a terrain by two watchtowers, Covering a set of line segments with a few squares, Covering a set of line segments with a few squares, THE ANCHORED VORONOI DIAGRAM: STATIC, DYNAMIC VERSIONS AND APPLICATIONS, The bi‐criteria doubly weighted center‐median path problem on a tree, Geometric optimization and sums of algebraic functions, Approximating Minimization Diagrams and Generalized Proximity Search, Deletion in Abstract Voronoi Diagrams in Expected Linear Time., Unnamed Item, Unnamed Item, Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model, Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions, A crossing lemma for multigraphs, An efficient $k$ nearest neighbors searching algorithm for a query line., Bicriteria product design optimization: An efficient solution procedure using AND/OR trees, Constrained square-center problems, A Refined Definition for Groups of Moving Entities and Its Computation, Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, On the planar piecewise quadratic 1-center problem, Unreliable point facility location problems on networks, Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor, Connect the Dot: Computing Feed-Links with Minimum Dilation, Information Spreading by Mobile Particles on a Line, On incremental rendering of silhouette maps of a polyhedral scene, On finding widest empty curved corridors, PROBABILISTIC ANALYSIS FOR DISCRETE ATTRIBUTES OF MOVING POINTS, On topological changes in the Delaunay triangulation of moving points, The overlay of lower envelopes and its applications, Cutting algebraic curves into pseudo-segments and applications, Nondegenerate spheres in four dimensions, Computing depth orders for fat objects and related problems, Extremal functions of forbidden multidimensional matrices, Connected component and simple polygon intersection searching, Topological stability of kinetic $k$-centers, Four Soviets walk the dog: improved bounds for computing the Fréchet distance, A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment, Queries on Voronoi diagrams on moving points, On Ray Shooting for Triangles in 3-Space and Related Problems, Minmax regret maximal covering location problems with edge demands, Nearest-neighbor searching under uncertainty. I, Spanners for Directed Transmission Graphs, Constructing sparse Davenport-Schinzel sequences, Erdős-Hajnal conjecture for graphs with bounded VC-dimension, A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane, Continuous-Time Moving Network Voronoi Diagram, A crossing lemma for multigraphs, Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location, PRECISE VORONOI CELL EXTRACTION OF FREE-FORM PLANAR PIECEWISE C¹-CONTINUOUS CLOSED RATIONAL CURVES, OPTIMAL VORONOI DIAGRAM CONSTRUCTION WITH n CONVEX SITES IN THREE DIMENSIONS, Smarter Lions: Efficient Cooperative Pursuit in General Bounded Arenas, Unnamed Item, Near-linear approximation algorithms for geometric hitting sets, Approximating the k-Level in Three-Dimensional Plane Arrangements, Three problems about simple polygons, On computing the convex hull of (piecewise) curved objects, On 2-site Voronoi diagrams under geometric distance functions, Trajectory planning for an articulated probe, Eliminating depth cycles among triangles in three dimensions, Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications, Constructing planar support for non-piercing regions, Empty squares in arbitrary orientation among points, Robot motion planning, Stabbing Convex Polygons with a Segment or a Polygon, Convex equipartitions: the spicy chicken theorem, On the number of permutations avoiding a given pattern, Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind, A 2D advancing-front Delaunay mesh refinement algorithm, Characterization and computation of feasible trajectories for an articulated probe with a variable-length end segment, On separating points by lines, THE ONION DIAGRAM: A VORONOI-LIKE TESSELLATION OF A PLANAR LINE SPACE AND ITS APPLICATIONS, On the number of regular vertices of the union of Jordan regions, Robust location problems with pos/neg weights on a tree, Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments, Dynamic proximity calculations for situation awareness, Visibility maps of segments and triangles in 3D, Location of weighted anti-ordered median straight lines with Euclidean distances, Improved output-sensitive snap rounding, Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D, AN EXPERIMENTAL STUDY OF ON-LINE METHODS FOR ZONE CONSTRUCTION IN ARRANGEMENTS OF LINES IN THE PLANE, Bichromatic 2-center of pairs of points, Proximity problems on line segments spanned by points, Parametric search: three new applications, Locating an obnoxious plane, On the complexity of the $k$-level in arrangements of pseudoplanes, Union of hypercubes and 3D Minkowski sums with random sizes, Unnamed Item, On Kinetic Delaunay Triangulations, Subdivision Drawings of Hypergraphs, Maintaining the extent of a moving point set, Learning big (image) data via coresets for dictionaries, Linear bounds on matrix extremal functions using visibility hypergraphs, Computing a Minimum-Width Square Annulus in Arbitrary Orientation, A relationship between generalized Davenport-Schinzel sequences and interval chains, CONSTRUCTING OPTIMAL HIGHWAYS, Space-Aware Reconfiguration, Minimum Width Color Spanning Annulus, Efficient randomized algorithms for some geometric optimization problems, A new technique for analyzing substructures in arrangements of piecewise linear surfaces, SMALLEST COLOR-SPANNING OBJECT REVISITED, Crossing patterns of semi-algebraic sets, Faster algorithms for growing prioritized disks and rectangles, One-way and round-trip center location problems, Dynamic data structures for fat objects and their applications, Computing obnoxious 1-corner polygonal chains, Counting and representing intersections among triangles in three dimensions, Extremal point queries with lines and line segments and related problems, A lower bound on Voronoi diagram complexity., Abstract Voronoi Diagrams from Closed Bisecting Curves, On the zone of the boundary of a convex body, A simple, faster method for kinetic proximity problems, Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems, Reporting intersecting pairs of convex polytopes in two and three dimensions, On the complexity of randomly weighted multiplicative Voronoi diagrams