An efficient algorithm for finding the minimum norm point in the convex hull of a finite point set in the plane

Naoki Makimoto; Ikuo Nakagawa; Akihisa Tamura

doi:10.1016/0167-6377(94)90019-1

An efficient algorithm for finding the minimum norm point in the convex hull of a finite point set in the plane

Naoki Makimoto, Ikuo Nakagawa, Akihisa Tamura

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

The minimum norm point problem is to find the minimum norm point in the convex hull of given n points in the d-dimensional Euclidean space. In this note, we propose an efficient algorithm for the two dimensional case and evaluate its time complexity.

Original language	English
Pages (from-to)	33-40
Number of pages	8
Journal	Operations Research Letters
Volume	16
Issue number	1
DOIs	https://doi.org/10.1016/0167-6377(94)90019-1
Publication status	Published - 1994 Aug
Externally published	Yes

Keywords

Computational complexity
Convex hull
Minimum norm point

ASJC Scopus subject areas

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

Access to Document

10.1016/0167-6377(94)90019-1

Cite this

@article{315d771764c34202a6eeb441070d9a2b,

title = "An efficient algorithm for finding the minimum norm point in the convex hull of a finite point set in the plane",

abstract = "The minimum norm point problem is to find the minimum norm point in the convex hull of given n points in the d-dimensional Euclidean space. In this note, we propose an efficient algorithm for the two dimensional case and evaluate its time complexity.",

keywords = "Computational complexity, Convex hull, Minimum norm point",

author = "Naoki Makimoto and Ikuo Nakagawa and Akihisa Tamura",

year = "1994",

month = aug,

doi = "10.1016/0167-6377(94)90019-1",

language = "English",

volume = "16",

pages = "33--40",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - An efficient algorithm for finding the minimum norm point in the convex hull of a finite point set in the plane

AU - Makimoto, Naoki

AU - Nakagawa, Ikuo

AU - Tamura, Akihisa

PY - 1994/8

Y1 - 1994/8

N2 - The minimum norm point problem is to find the minimum norm point in the convex hull of given n points in the d-dimensional Euclidean space. In this note, we propose an efficient algorithm for the two dimensional case and evaluate its time complexity.

AB - The minimum norm point problem is to find the minimum norm point in the convex hull of given n points in the d-dimensional Euclidean space. In this note, we propose an efficient algorithm for the two dimensional case and evaluate its time complexity.

KW - Computational complexity

KW - Convex hull

KW - Minimum norm point

UR - http://www.scopus.com/inward/record.url?scp=0004705467&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0004705467&partnerID=8YFLogxK

U2 - 10.1016/0167-6377(94)90019-1

DO - 10.1016/0167-6377(94)90019-1

M3 - Article

AN - SCOPUS:0004705467

SN - 0167-6377

VL - 16

SP - 33

EP - 40

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

An efficient algorithm for finding the minimum norm point in the convex hull of a finite point set in the plane

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this