Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Partitioning a polygonal region into trapezoids
View through CrossRef
The problem of partitioning a polygonal region into a minimum number of trapezoids with two horizontal sides is discussed. A triangle with a horizontal side is considered to be a trapezoid with two horizontal sides one of which is degenerate. First, a method of achieving a minimum partition is presented. The number
M
* of the trapezoids in the minimum partition of a polygonal region
P
is shown to be
M
*
=
n
+
w
-
h
-
d
- 1, where
n
,
w
, and
h
are the number of vertices, windows (holes), and horizontal edges of
P
, respectively, and
d
is the cardinality of a maximum independent set of the straight-lines-in-the-plane graph associated with
P
. Next, this problem is shown to be polynomially equivalent to the problem of finding a maximum independent set of a straight-lines-in-the-plane graph, and consequently, it is shown to be NP-complete. However, for a polygonal region without windows, an
O
(
n
2
)-time algorithm for partitioning it into a minimum number of trapezoids is presented. Finally, an
O
(
n
log
n
)-time approximation algorithm with the performance bound 3 is presented.
Association for Computing Machinery (ACM)
Title: Partitioning a polygonal region into trapezoids
Description:
The problem of partitioning a polygonal region into a minimum number of trapezoids with two horizontal sides is discussed.
A triangle with a horizontal side is considered to be a trapezoid with two horizontal sides one of which is degenerate.
First, a method of achieving a minimum partition is presented.
The number
M
* of the trapezoids in the minimum partition of a polygonal region
P
is shown to be
M
*
=
n
+
w
-
h
-
d
- 1, where
n
,
w
, and
h
are the number of vertices, windows (holes), and horizontal edges of
P
, respectively, and
d
is the cardinality of a maximum independent set of the straight-lines-in-the-plane graph associated with
P
.
Next, this problem is shown to be polynomially equivalent to the problem of finding a maximum independent set of a straight-lines-in-the-plane graph, and consequently, it is shown to be NP-complete.
However, for a polygonal region without windows, an
O
(
n
2
)-time algorithm for partitioning it into a minimum number of trapezoids is presented.
Finally, an
O
(
n
log
n
)-time approximation algorithm with the performance bound 3 is presented.
Related Results
CATALAN'S TRAPEZOIDS
CATALAN'S TRAPEZOIDS
Named after the French–Belgian mathematician Eugène Charles Catalan, Catalan's numbers arise in various combinatorial problems [12]. Catalan's triangle, a triangular array of numbe...
Polygonal spatiotemporal optical vortices wavepackets with a prescribed vortex structure
Polygonal spatiotemporal optical vortices wavepackets with a prescribed vortex structure
Spatiotemporal optical vortices (STOVs) are a type of light beams that carry transverse orbital angular momentum (T-OAM), enabling the generation and control of additional degrees ...
A Topological Approach to Partitioning Flow Networks for Parallel Simulation
A Topological Approach to Partitioning Flow Networks for Parallel Simulation
<div>System partitioning for effective simulation of civil infrastructure flow networks on parallel processors is a nontrivial problem. Arbitrary partitioning focused only on...
A Topological Approach to Partitioning Flow Networks for Parallel Simulation
A Topological Approach to Partitioning Flow Networks for Parallel Simulation
<div>System partitioning for effective simulation of civil infrastructure flow networks on parallel processors is a nontrivial problem. Arbitrary partitioning focused only on...
Karakter Tanaman Tembakau Temanggung yang Berpengaruh Terhadap Hasil dan Mutu Rajangan Kering
Karakter Tanaman Tembakau Temanggung yang Berpengaruh Terhadap Hasil dan Mutu Rajangan Kering
<p>Peningkatan hasil dan mutu rajangan kering tembakau temanggung dapat dilakukan bila telah diketahui ka-rakter tanaman yang berpengaruh terhadap hasil dan mutu rajangan ker...
The Complexity of Drawing a Graph in a Polygonal Region
The Complexity of Drawing a Graph in a Polygonal Region
We prove that the following problem is complete for the existential theory of the reals:
Given a planar graph and a polygonal region, with some vertices of the graph assigned to po...
Impacts of microtopographic snow-redistribution and lateral subsurface processes
on hydrologic and thermal states in an Arctic polygonal ground ecosystem
Impacts of microtopographic snow-redistribution and lateral subsurface processes
on hydrologic and thermal states in an Arctic polygonal ground ecosystem
Abstract. Microtopographic features, such as polygonal ground, are characteristic sources of landscape heterogeneity in the Alaskan Arctic coastal plain. Here, we analyze the effec...
Near-Data Source Graph Partitioning
Near-Data Source Graph Partitioning
Recently, numerous graph partitioning approaches have been proposed to distribute a big graph to machines in a cluster for distributed computing. Due to heavy communication overhea...