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
Seismic characteristics of polygonal fault systems in the Great South Basin, New Zealand
Seismic characteristics of polygonal fault systems in the Great South Basin, New Zealand
Abstract
A well-developed multi-tier polygonal fault system is located in the Great South Basin offshore New Zealand’s South Island. The system has been characterise...
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...
Research on Wheel Polygonal Wear of Metro Vehicles Based on Wheel/Rail Vertical Coupling
Research on Wheel Polygonal Wear of Metro Vehicles Based on Wheel/Rail Vertical Coupling
Wheel polygonal wear is a critical form of non-uniform tread degradation in metro systems, leading to abnormal vibration, noise, and accelerated deterioration of wheel-rail compone...
Detection, quantification, and investigation of the red blood cell partitioning of cryptolepine hydrochloride
Detection, quantification, and investigation of the red blood cell partitioning of cryptolepine hydrochloride
Context: The fight against malaria is limited by the development of resistance of Plasmodium to medication. This has led to an urgent search for alternative medicinal agents. Aims...
Construction Period and Characteristics of Polygonal Buildings during the Three Kingdoms to the Unified Silla Dynasty Periods
Construction Period and Characteristics of Polygonal Buildings during the Three Kingdoms to the Unified Silla Dynasty Periods
The polygonal buildings from the Three Kingdoms Period are deemed related to religious buildings associated with temples, namely wooden pagodas. With the investigation of a presume...
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 ...
Positive region: An enhancement of partitioning attribute based rough set for categorical data
Positive region: An enhancement of partitioning attribute based rough set for categorical data
Datasets containing multi-value attributes are often involved in several domains, like pattern recognition, machine learning and data mining. Data partition is required in such cas...
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...