Article

Free access

Generalizing ham sandwich cuts to equitable subdivisions

Authors:

Sergei Bespamyatnikh,

David Kirkpatrick,

Jack SnoeyinkAuthors Info & Claims

SCG '99: Proceedings of the fifteenth annual symposium on Computational geometry

Pages 49 - 58

https://doi.org/10.1145/304893.304909

Published: 13 June 1999 Publication History

PDF eReader

References

[1]

P. Agarwal and M. Sharir. Arrangements. In JSrg-Riidiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 1998.

Google Scholar

[2]

I. B~r~ny. Geometric and combinatorial applications of Borsuk's theorem. In J. Pach, editor, New Trends in Discrete and Computational Geometry, volume l0 of Algorithms and Cbmbinatorics, pages 235-249. Springer- Verlag, 1993.

Google Scholar

[3]

T. K. Dey. Improved bounds on planar ksets and related problems. Discrete Comput. Geom., 19:373-382, 1998.

Crossref

Google Scholar

[4]

M. Diaz and J. O'Rourke. Ham-sandwich sectioning of polygons. In Proc. 2nd CCCG, pages 282-286, 1990.

Google Scholar

[5]

D. P. Dobkin and H. Edelsbrunner. Hamsandwich theorems applied to intersection problems. In Proc. l Oth Internat. Workshop Graph-Theoret. Concepts Comput. Sci., pages 88-99. 1984.

Google Scholar

[6]

H. Edelsbrunner and R. Waupotitsch. Computing a ham-sandwich cut in two dimensions. J. Symbolic Comput., 2:171-178, 1986.

Digital Library

Google Scholar

[7]

H. Edelsbrunner and Emo Welzl. Constructing belts in two-dimensional arrangements with applications. SIAM J. Comput., 15"271-284, 1986.

Digital Library

Google Scholar

[8]

J. E. Goodman, J. Pach, and C. K. Yap. Mountain climbing, ladder moving, and the ring width of a polygon. Amer. Math. Monthly, 96"494-510, 1989.

Digital Library

Google Scholar

[9]

H. Uehara, H. Ito and M. Yokoyama. 2- dimension ham sandwich .theorem for partitioning into three convex pieces (extended abstract). In Proc.of the Japan Conference on Discrete and Comp. Geom.~ pages 69-73, 1998.

Digital Library

Google Scholar

[10]

A. Kaneko and M. Kano. Balanced partitions of two sets of points in the plane. In CCCG, 1998. Extended Abstract.

Google Scholar

[11]

C.-Y. Lo, J. Matou~ek, and W. Steiger. Hamsandwich cuts in Rd. In Proc. 24th Annu. A CM Sympos. Theory Comput., pages 539- 545, 1992.

Digital Library

Google Scholar

[12]

C.-Y. Lo, J. Matou~ek, and W. L. Steiger. Algorithms for ham-sandwich cuts. Discrete Comput. Geom., 11:433-452, 1994.

Crossref

Google Scholar

[13]

C.-Y. Lo and W. Steiger. An optimal-time algorithm for ham-sandwich cuts in the plane. In Proc. 2nd Canad. Conf. Comput. Geom., pages 5-9, 1990.

Google Scholar

[14]

M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Cornput. Syst. Sci., 23"166-204, 1981.

Google Scholar

[15]

T. Sakai. Radial partitions of point sets in r2. In Proc. of the Japan Conference on Discrete and Comp. Geom., 1998.

Google Scholar

[16]

W. Steiger. Algorithms for ham sandwich cuts. In Proc. 5th CCCG, page 48, 1993.

Google Scholar

[17]

R. T. Zivaljevi~. Topological methods. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 11, pages 209-224. CRC Press LLC, Boca Raton, FL, 1997.

Digital Library

Google Scholar

[18]

R. T. Zivaljevid and S. T. Vredica. An extension of the ham sandwich theorem. Bull. London Math. Soc., 22"183-186, 1990.

Google Scholar

Cited By

View all

Roldán-Pensado ESoberón P(2021)A survey of mass partitionsBulletin of the American Mathematical Society10.1090/bull/1725Online publication date: 24-Feb-2021
https://doi.org/10.1090/bull/1725
Venkata Narasimha KKivelevitch ESharma BKumar M(2013)An ant colony optimization technique for solving min–max Multi-Depot Vehicle Routing ProblemSwarm and Evolutionary Computation10.1016/j.swevo.2013.05.00513(63-73)Online publication date: Dec-2013
https://doi.org/10.1016/j.swevo.2013.05.005
Narasimha KKivelevitch EKumar M(2012)Ant Colony optimization technique to Solve the min-max multi depot vehicle routing problem2012 American Control Conference (ACC)10.1109/ACC.2012.6315583(3980-3985)Online publication date: Jun-2012
https://doi.org/10.1109/ACC.2012.6315583
Show More Cited By

Index Terms

Generalizing ham sandwich cuts to equitable subdivisions

Recommendations

Generalizing Ham Sandwich Cuts to Equitable Subdivisions

We prove a generalization of the famous Ham Sandwich Theorem for the plane. Given gn red points and gm blue points in the plane in general position, there exists an equitable subdivision of the plane into g disjoint convex polygons, each of which ...
Damage-Tolerance Characteristics of Composite Fuselage Sandwich Structures With Thick Facesheets
Buckling Analysis of Debonded Sandwich Panel Under Compression

Comments

Information & Contributors

Information

Published In

SCG '99: Proceedings of the fifteenth annual symposium on Computational geometry

June 1999

432 pages

ISBN:1581130686

DOI:10.1145/304893

Chairman:
Victor Milenkovic
Univ. of Miami, Coral Gables, FL

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SoCG99

Sponsor:

SoCG99: The Symposium on Computational Geometry

June 13 - 16, 1999

Florida, Miami Beach, USA

Acceptance Rates

SCG '99 Paper Acceptance Rate 44 of 103 submissions, 43%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
513
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)9

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Roldán-Pensado ESoberón P(2021)A survey of mass partitionsBulletin of the American Mathematical Society10.1090/bull/1725Online publication date: 24-Feb-2021
https://doi.org/10.1090/bull/1725
Venkata Narasimha KKivelevitch ESharma BKumar M(2013)An ant colony optimization technique for solving min–max Multi-Depot Vehicle Routing ProblemSwarm and Evolutionary Computation10.1016/j.swevo.2013.05.00513(63-73)Online publication date: Dec-2013
https://doi.org/10.1016/j.swevo.2013.05.005
Narasimha KKivelevitch EKumar M(2012)Ant Colony optimization technique to Solve the min-max multi depot vehicle routing problem2012 American Control Conference (ACC)10.1109/ACC.2012.6315583(3980-3985)Online publication date: Jun-2012
https://doi.org/10.1109/ACC.2012.6315583
Trajcevski GGhica OScheuermann PTamassia RCruz IBalazinska MYang JDiao YJensen C(2008)Alternating multiple tributaries + deltasProceedings of the 5th workshop on Data management for sensor networks10.1145/1402050.1402057(28-34)Online publication date: 24-Aug-2008
https://dl.acm.org/doi/10.1145/1402050.1402057
Blagojević PVrećica SŽivaljević R(2008)Computational topology of equivariant maps from spheres to complements of arrangementsTransactions of the American Mathematical Society10.1090/S0002-9947-08-04679-5361:2(1007-1038)Online publication date: 19-Aug-2008
https://doi.org/10.1090/S0002-9947-08-04679-5
Sakai TNara CUrrutia J(2003)Equal area polygons in convex bodiesProceedings of the 2003 Indonesia-Japan joint conference on Combinatorial Geometry and Graph Theory10.1007/978-3-540-30540-8_17(146-158)Online publication date: 13-Sep-2003
https://dl.acm.org/doi/10.1007/978-3-540-30540-8_17
Chan T(2000)On levels in arrangements of curvesProceedings 41st Annual Symposium on Foundations of Computer Science10.1109/SFCS.2000.892109(219-227)Online publication date: 2000
https://doi.org/10.1109/SFCS.2000.892109
Ito HUehara HYokoyama M(2000)2-Dimension Ham Sandwich Theorem for Partitioning into Three Convex PiecesDiscrete and Computational Geometry10.1007/978-3-540-46515-7_11(129-157)Online publication date: 2000
https://doi.org/10.1007/978-3-540-46515-7_11

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations