Andere Kunden interessierten sich auch für
![Perturbation-based Extremum Seeking Control Design for a Class of Nonlinear systems]( "Perturbation-based Extremum Seeking Control Design for a Class of Nonlinear systems")
Perturbation-based Extremum Seeking Control Design for a Class of Nonlinear systems23,99 €![Practical Plane and Solid Geometry: For Use in Science Classes and Higher and Middle Class Schools]( "Practical Plane and Solid Geometry: For Use in Science Classes and Higher and Middle Class Schools")
Practical Plane and Solid Geometry: For Use in Science Classes and Higher and Middle Class Schools34,99 €![The Case of the Missing Class Pet]( "The Case of the Missing Class Pet")
The Case of the Missing Class Pet38,99 €![Differential Geometry]( "Differential Geometry")
Differential Geometry44,99 €![Bordism of Diffeomorphisms and Related Topics]( "Bordism of Diffeomorphisms and Related Topics")
Bordism of Diffeomorphisms and Related Topics21,99 €![Symplectic Geometry and Analytical Mechanics]( "Symplectic Geometry and Analytical Mechanics")
Symplectic Geometry and Analytical Mechanics150,99 €![Unsolved Problems in Geometry]( "Unsolved Problems in Geometry")
Unsolved Problems in Geometry108,99 €
Given a simple polygon P and an integer K 1, we
want to compute the set of
straight lines in the Cartesian plane that cut this
polygon into exactly K simple
polygons. We call this set of lines a K-separator and
call this problem the K-separator
problem.
We present an algorithm that finds the K-separators
of an n-vertex simple polygon,
for all K 0, in O(n2) total time.
We prove that the decision problem given an integer K 2 and an edge of the
polygon, is there a line through this edge that cuts
the polygon in exactly K pieces?, is
3SUM-HARD. For the special case when K = 2, we show
that the decision problem
can be solved in O(n log(n)) time.
Several other complexity results may be obtained. We
suspect that the problem
of finding the cell of maximum depth is also
3SUM-hard, and as a corollary the
problem of identifying the line that cuts the polygon
in the maximum possible number
of pieces is also 3SUM-hard.
want to compute the set of
straight lines in the Cartesian plane that cut this
polygon into exactly K simple
polygons. We call this set of lines a K-separator and
call this problem the K-separator
problem.
We present an algorithm that finds the K-separators
of an n-vertex simple polygon,
for all K 0, in O(n2) total time.
We prove that the decision problem given an integer K 2 and an edge of the
polygon, is there a line through this edge that cuts
the polygon in exactly K pieces?, is
3SUM-HARD. For the special case when K = 2, we show
that the decision problem
can be solved in O(n log(n)) time.
Several other complexity results may be obtained. We
suspect that the problem
of finding the cell of maximum depth is also
3SUM-hard, and as a corollary the
problem of identifying the line that cuts the polygon
in the maximum possible number
of pieces is also 3SUM-hard.