Partitioning with two lines in the plane

DOI10.1016/0196-6774(85)90011-2zbMath0582.51013OpenAlexW2061705188WikidataQ56428478 ScholiaQ56428478MaRDI QIDQ3704524

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

linear programminglinear time algorithmcomputational geometryham sandwich problempoints in Euclidean plane

Mathematics Subject Classification ID

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

Related Items (30)

Algorithms for ham-sandwich cuts ⋮ Selecting distances in the plane ⋮ Computing a centerpoint of a finite planar set of points in linear time ⋮ Partitioning point sets in arbitrary dimension ⋮ Select with Groups of 3 or 4 ⋮ Computing a ham-sandwich cut in two dimensions ⋮ Edge-skeletons in arrangements with applications ⋮ Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem ⋮ Halfplanar range search in linear space and \(O(n^{0.695})\) query time ⋮ A survey of mass partitions ⋮ Point Selections and Weak ε-Nets for Convex Hulls ⋮ Discrete geometry on colored point sets in the plane -- a survey ⋮ Generalized ham-sandwich cuts ⋮ Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\) ⋮ Ham-sandwich cuts for abstract order types ⋮ Unnamed Item ⋮ Testing convexity of figures under the uniform distribution ⋮ Bisections and ham-sandwich cuts of convex polygons and polyhedra ⋮ On strong centerpoints ⋮ Algorithms for bivariate zonoid depth ⋮ The power and limitations of uniform samples in testing properties of figures ⋮ Weighted search in the plane ⋮ Separating collections of points in Euclidean spaces ⋮ Uneven splitting of ham sandwiches ⋮ Dynamic partition trees ⋮ On a problem about quadrant-depth ⋮ Points with large \(\alpha \)-depth ⋮ Dynamic ham-sandwich cuts in the plane ⋮ Selection Algorithms with Small Groups ⋮ Dynamic partition trees

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