Partitioning with two lines in the plane

DOI10.1016/0196-6774(85)90011-2MaRDI QIDQ3704524zbMATH OpenOpenAlexWikidataFDO

Authors Nimrod Megiddo

Publication date 1985

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(85)90011-2

zbMATH Keywords

computational geometryham sandwich problemlinear programminglinear time algorithmpoints in Euclidean plane

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to geometry (51-04) Euclidean geometries (general) and generalizations (51M05) Geometric constructions in real or complex geometry (51M15) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Recommendations

• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• OPTIMAL LINE BIPARTITIONS OF POINT SETS
• Optimal line bipartitions of point sets
• Computing a ham-sandwich cut in two dimensions
• A fast planar partition algorithm. I

Cited in

(45)

• Points with large \(\alpha \)-depth
• Dynamic ham-sandwich cuts in the plane
• Partitioning point sets in arbitrary dimension
• Computing a ham-sandwich cut in two dimensions
• Edge-skeletons in arrangements with applications
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Bisections and ham-sandwich cuts of convex polygons and polyhedra
• Algorithms for ham-sandwich cuts
• Computing a centerpoint of a finite planar set of points in linear time
• Improved algorithms for uniform partitions of points
• Bisecting three classes of lines
• Balanced convex partitions of lines in the plane
• Selecting distances in the plane
• Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
• Algorithms for bivariate zonoid depth
• Three-clustering of points in the plane.
• Discrete geometry on colored point sets in the plane -- a survey
• Select with groups of 3 or 4
• scientific article; zbMATH DE number 3911765 (Why is no real title available?)
• scientific article; zbMATH DE number 1262793 (Why is no real title available?)
• Point Selections and Weak ε-Nets for Convex Hulls
• scientific article; zbMATH DE number 1522945 (Why is no real title available?)
• OPTIMAL LINE BIPARTITIONS OF POINT SETS
• On strong centerpoints
• Selection Algorithms with Small Groups
• Practical low-dimensional halfspace range space sampling
• Dynamic partition trees
• A survey of mass partitions
• Fair Partitioning by Straight Lines
• Testing convexity of figures under the uniform distribution
• Generalized ham-sandwich cuts
• Partitioning axis-parallel lines in 3D
• Optimal line bipartitions of point sets
• New two-line arrays representing partitions
• The power and limitations of uniform samples in testing properties of figures
• Weighted search in the plane
• Separating collections of points in Euclidean spaces
• Eight-partitioning points in 3D, and efficiently too
• Eight-partitioning points in 3D, and efficiently too
• A linear time algorithm for the maximum overlap of two convex polygons under translation
• Dynamic partition trees
• Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\)
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Uneven splitting of ham sandwiches
• On a problem about quadrant-depth

This page was built for publication: Partitioning with two lines in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3704524)