Loading...
Please wait, while we are loading the content...
Similar Documents
SERIE B INFORMATIK Algorithms for Ham Sandwich Cuts
| Content Provider | Semantic Scholar |
|---|---|
| Author | Matou, Ji r Steiger, William |
| Copyright Year | 2009 |
| Abstract | Given disjoint sets P P Pd in R d with n points in total a ham sandwich cut is a hyperplane that simultaneously bisects the Pi We present algorithms for nding ham sandwich cuts in every dimension d When d the algorithm is optimal having complexity O n For dimension d the bound on the running time is proportional to the worst case time needed for constructing a level in an arrangement of n hyperplanes in dimension d This in turn is related to the number of k sets in R With the current estimates we get complexity close to O n for d roughly O n for d and O n a d for some a d going to zero as d increases for larger d We also give a linear time algorithm for ham sandwich cuts in R when the three sets are suitably separated A preliminary version of the results of this paper appeared in and Part of this research by J M was done while he was visiting the School of Mathematics Georgia Institute of Technology Atlanta and part of his work on this paper was supported by Humboldt Research Fellowship W S expresses gratitude to the NSF DIMACS Center at Rutgers and his research was supported in part by NSF grants CCR and CCR AT T Bell Laboratories Murray Hill NJ USA Department of Applied Mathematics Charles University Malostransk e n am Praha Czechoslovakia and Free University of Berlin Arnimallee W Berlin Germany Rutgers University Dept of Computer Science New Brunswick NJ USA Introduction and Summary A hyperplane h is said to bisect a set P of n points in R if no more than n points of P lie in either of the open halfspaces de ned by h It is no loss of generality to assume n odd since otherwise we may delete any point x and observe that any hyperplane that bisects P n fxg also bisects P If P is a disjoint union of d sets P Pd a ham sandwich cut is a hyperplane that simultaneously bisects all the Pi The ham sandwich theorem see for example guarantees the existence of such a cut Here we focus on the algorithmic question which asks for e cient procedures for computing a cut and for bounds on the complexity of this task Throughout we use a model of computation where any arithmetic operation or comparison is charged unit cost the real RAM model In two dimensions a ham sandwich cut is a line h that bisects P and P For the linearly separated case where the convex hulls of P and P do not intersect Megiddo gave an algorithm to compute h that runs in O n steps Megiddo s algorithm gives an optimal solution to a partitioning problem posed by Willard namely to nd lines and that separate n given points into quadrants containing at most n points each The rst line may be any say horizontal line partitioning the points evenly easily obtained in O n steps The second line is a ham sandwich cut for the points P above and P below obtained in linear time by Megiddo s algorithm Edelsbrunner and Waupotitsch modi ed Megiddo s method for the general planar case Their algorithm can compute h in time O n log n Earlier Cole Sharir and Yap had described a procedure that may now be seen to have the same complexity in view of the existence of a logarithmic depth sorting network In this paper we prove the following result see also Proposition Given two sets of points P and P in R jP j jP j n a ham sandwich cut can be computed in O n time The proof consists of an optimal linear time algorithm which thus settles the complexity question for two dimensional ham sandwich cuts In three and higher dimensions much less was known The brute force approach has complexity O n the odd cardinality assumption forces a cut to contain a point from each Pi and we can check the hyperplane corresponding to each possible d tuple in linear time It is also not too di cult to give an O n algorithm by constructing the arrangements of hyperplanes dual to the points of P see Section for the dual formulation of the problem Edelsbrunner described a related problem of nding two planes that simul taneously divide each of two given sets of points in R into four equal sized subsets the points were required to satisfy a special separation condition He gives an algo rithm with running time O t n log n where t n denotes the maximal number of n sets possessed by any set of n points in R see also section In Section we show how to generalize the ideas used in Proposition to di mension d and describe an algorithm with complexity O n The running Algorithms for Ham Sandwich Cuts time can be further decreased using relatively complicated ray shooting methods for construction of levels in hyperplane arrangements We prove the following Proposition Given n points in R which are partitioned into d sets P Pd in R a ham sandwich cut can be computed in time proportional to the worst case time needed to construct a given level in the arrangement of n given hyperplanes in R The latter problem i requires at least n time ii is easy to solve in O n time iii can be solved within the following bounds O n log n log n for d O n for d O n a d with certain small constant a d for d Finally for the case d if the sets are suitably separated the general algorithm can be modi ed so that it nds a ham sandwich cut in linear time This extends Megiddo s result to R Preliminaries and Notation We denote by S the coordinate hyperplane xd i e the x axis for d For a subset X S we denote by V X the vertical cylinder erected through X i e V X f x x xd xd R x xd Xg It is easier to look at a dual version of the ham sandwich problem We use the duality transform which maps the point p x xd to the nonvertical hyperplane f w wd wd x w xd wd xdg see for properties The ham sandwich cut problem then becomes the following Given a setH of hyperplanes in R partitioned into d classesH Hd jHij odd nd a point x which for each i d has no more than jHij of the hyperplanes of Hi below it and no more than jHij hy perplanes above To simplify our considerations we make some general position assumptions We suppose that every d tuple of hyperplanes of H meets in a unique point vertex and that no point in R is incident with more than d of the hyperplanes Also we assume that the vertical direction the direction of the xd axis is a generic one i e that the vertical projections of all vertices on the coordinate hyperplane xd are all distinct This is no loss of generality as one may use some variant of simulation of simplicity see to handle the general case Given a set H of hyperplanes in R they partition the space into a complex of convex cells called the arrangement of H An important concept for us will be the p level in the arrangement of H denoted by Lp H This is de ned as the closure of the set of all points which lie on a unique hyperplane of the arrangement and have exactly p hyperplanes below it In dimension the p level is a continuous piecewise linear function whose segments always coincide with one of the lines in the arrangement In higher dimensions the p level also consists of certain cells of the arrangement of H and thus it is a piecewise linear hypersurface in R When p b jHj c the Lp H is called the median level of the arrangement The dual version of the ham sandwich cut problem may be restated as follows Given a set H f ng of hyperplanes in R partitioned into d classes H Hd jHij odd nd an intersection point of the median levels of the arrangements of H Hd Such an intersection point will be a vertex in the arrangement of H whose d de ning hyperplanes contain precisely one hyperplane of each Hi A key feature used by our algorithms is the odd intersection property A set X S f x xd g has the odd intersection property with respect to levels i Lpi Hi if j d V X j is odd i e the levels intersect an odd number of times in the cylinder erected through X note that the set d is nite by our general position assumption The running time of our algorithm will depend on the time needed for construc tion of levels in arrangements of hyperplanes this time in turn depends on the combinatorial complexity of these levels We review the known results Let ed n k denote the maximum possible number of vertices of the k level in an arrangement of n hyperplanes in R and let ed n maxfed n k k ng It is well known that ed n k is proportional to the maximum number of k sets of an n point set in R The k set problem has been extensively studied see and It is known that ed n n log n and it is conjectured that this bound is close to the truth The known upper bounds seem much weaker however It was shown that e n O n log n that e n O n and in general ed n O n d for some small positive constant d E cient output sensitive algorithms for level construction are known in dimen sions and a level of complexity b can be constructed in time O n log n b log n for d and in time O n bn for d an arbitrarily small positive constant For d the e ciency of the algorithm of gets worse it guarantees that if the complexity of the level is O n d for some d then the level can be constructed in O n d d d time |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://edocs.fu-berlin.de/docs/servlets/MCRFileNodeServlet/FUDOCS_derivate_000000000249/1992_20.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
