MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Equitable 3-cuttings in two and three dimensions

Sergei Bespamyatnikh
University of British Columbia, Dept. of Computer Scienc
Talk
AG 1, AG 4  
AG Audience
English

Date, Time and Location

Monday, 20 December 99
15:45
-- Not specified --
45
HS 001
Saarbrücken

Abstract

We investigate the generalization the famous Ham Sandwich Theorem

for the plane that states that, for finite sets of red and blue points
in the plane, there exists a line dividing both red and blue points
into sets of equal size. We consider equitable 3-cuttings of 2 arbitrary
mass distributions in the plane (partitions of the plane into 3 sectors
with a common apex such that each sector contains 1/3 of the 2 mass
distributions). We prove the existence of a continuum of equitable
3-cuttings that satisfy some closure property. This permits us to
generalize earlier results on both convex and non-convex equitable
3-cuttings with additional constraints. It is also used to prove
the existence of an equitable 3-cutting of 3 masses in 3 dimensions.

We present algorithms to compute equitable 3-cuttings in two and three
dimensions for discrete versions of problems

Contact

Raimund Seidel
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Computational Geometry, Ham-Sandwich Cuts