The search functionality is under construction.

The search functionality is under construction.

This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph *G* of *n* vertices, is there a partition of the vertex set into *k* disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for *k* = 3. The case of *k*=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for *k* *k* is a fixed constant. For the case *k*=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.

- Publication
- IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.418-427

- Publication Date
- 2000/03/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- INVITED SURVEY PAPER

- Category
- Algorithms for Geometric Problems

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Tetsuo ASANO, "Effective Use of Geometric Information for Clustering and Related Topics" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 3, pp. 418-427, March 2000, doi: .

Abstract: This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph *G* of *n* vertices, is there a partition of the vertex set into *k* disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for *k* = 3. The case of *k*=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for *k* *k* is a fixed constant. For the case *k*=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.

URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_418/_p

Copy

@ARTICLE{e83-d_3_418,

author={Tetsuo ASANO, },

journal={IEICE TRANSACTIONS on Information},

title={Effective Use of Geometric Information for Clustering and Related Topics},

year={2000},

volume={E83-D},

number={3},

pages={418-427},

abstract={This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph *G* of *n* vertices, is there a partition of the vertex set into *k* disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for *k* = 3. The case of *k*=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for *k* *k* is a fixed constant. For the case *k*=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.

keywords={},

doi={},

ISSN={},

month={March},}

Copy

TY - JOUR

TI - Effective Use of Geometric Information for Clustering and Related Topics

T2 - IEICE TRANSACTIONS on Information

SP - 418

EP - 427

AU - Tetsuo ASANO

PY - 2000

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E83-D

IS - 3

JA - IEICE TRANSACTIONS on Information

Y1 - March 2000

AB - This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph *G* of *n* vertices, is there a partition of the vertex set into *k* disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for *k* = 3. The case of *k*=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for *k* *k* is a fixed constant. For the case *k*=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.

ER -