Minimum polygonal separation
From MaRDI portal
Publication:1101685
DOI10.1016/0890-5401(88)90049-1zbMath0642.52004OpenAlexW2017921773MaRDI QIDQ1101685
Herbert Edelsbrunner, Franco P. Preparata
Publication date: 1988
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2142/74252
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (2) dimensions (including convex curves) (52A10)
Related Items
Geometric separability using orthogonal objects, Separability of imprecise points, Counterexample-guided predicate abstraction of hybrid systems, Separability by two lines and by nearly straight polygonal chains, SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS, A characterization of 2-threshold functions via pairs of prime segments, Separation and approximation of polyhedral objects, RED-BLUE SEPARABILITY PROBLEMS IN 3D, On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees, On the complexity of polyhedral separability, About the decidability of polyhedral separability in the lattice \(\mathbb {Z}^d\). Recognizing digital polyhedra with a prescribed number of faces, Separating Bichromatic Point Sets by Minimal Triangles with a Fixed Angle, Computational aspects of relaxation complexity: possibilities and limitations, Separating bichromatic point sets by L-shapes, Efficiently testing digital convexity and recognizing digital convex polygons, Separating bichromatic point sets in the plane by restricted orientation convex hulls, Starshaped sets, SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS, Sequential and parallel algorithms for finding a maximum convex polygon, SEPARABILITY OF POINT SETS BY k-LEVEL LINEAR CLASSIFICATION TREES, Parallel algorithms for separation of two sets of points and recognition of digital convex polygons, Separating objects in the plane by wedges and strips, COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS, Computational aspects of relaxation complexity, Finding minimal convex nested polygons
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing circular separability
- Finding the intersection of two convex polyhedra
- Linear Time Algorithms for Two- and Three-Variable Linear Programs
- Euclidean shortest paths in the presence of rectilinear barriers
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
- A linear algorithm for determining the separation of convex polyhedra
