Computing the widest empty boomerang

Boaz Ben-Moshe; Binay Bhattacharya; Qiaosheng Shi

Computing the widest empty boomerang

Boaz Ben-Moshe
, Binay Bhattacharya
, Qiaosheng Shi

פרסום מחקרי: תוצר מחקר מכנס › הרצאה › ביקורת עמיתים

תקציר

In this paper we consider the following obnoxious facility location problem: Given a set S of n points in the plane, and two special points a and b, find the 1-corner polygonal chain (also known as boomerang) connecting a and b such that its minimum distance to S is maximized. In other words: Find the widest empty polygonal chain of two edges having extremes anchored at a and b. We present a new O(n log n) algorithm which improves the previous O(n2) result [3].

שפה מקורית	אנגלית
עמודים	80-83
מספר עמודים	4
סטטוס פרסום	פורסם - 2005
פורסם באופן חיצוני	כן
אירוע	17th Canadian Conference on Computational Geometry, CCCG 2005 - Windsor, קנדה משך הזמן: 10 אוג׳ 2005 → 12 אוג׳ 2005

כנס

כנס	17th Canadian Conference on Computational Geometry, CCCG 2005
מדינה/אזור	קנדה
עיר	Windsor
תקופה	10/08/05 → 12/08/05

קבצים וקישורים אחרים

Link to publication in Scopus

פורמט ציטוט ביבליוגרפי

@conference{a4efafedd2aa4408bc93e0ebdb91ac82,

title = "Computing the widest empty boomerang",

abstract = "In this paper we consider the following obnoxious facility location problem: Given a set S of n points in the plane, and two special points a and b, find the 1-corner polygonal chain (also known as boomerang) connecting a and b such that its minimum distance to S is maximized. In other words: Find the widest empty polygonal chain of two edges having extremes anchored at a and b. We present a new O(n log n) algorithm which improves the previous O(n2) result [3].",

author = "Boaz Ben-Moshe and Binay Bhattacharya and Qiaosheng Shi",

note = "Publisher Copyright: {\textcopyright} 2005 Canadian Conference on Computational Geometry. All rights reserved.; 17th Canadian Conference on Computational Geometry, CCCG 2005 ; Conference date: 10-08-2005 Through 12-08-2005",

year = "2005",

language = "אנגלית",

pages = "80--83",

}

TY - CONF

T1 - Computing the widest empty boomerang

AU - Ben-Moshe, Boaz

AU - Bhattacharya, Binay

AU - Shi, Qiaosheng

PY - 2005

Y1 - 2005

N2 - In this paper we consider the following obnoxious facility location problem: Given a set S of n points in the plane, and two special points a and b, find the 1-corner polygonal chain (also known as boomerang) connecting a and b such that its minimum distance to S is maximized. In other words: Find the widest empty polygonal chain of two edges having extremes anchored at a and b. We present a new O(n log n) algorithm which improves the previous O(n2) result [3].

AB - In this paper we consider the following obnoxious facility location problem: Given a set S of n points in the plane, and two special points a and b, find the 1-corner polygonal chain (also known as boomerang) connecting a and b such that its minimum distance to S is maximized. In other words: Find the widest empty polygonal chain of two edges having extremes anchored at a and b. We present a new O(n log n) algorithm which improves the previous O(n2) result [3].

UR - https://www.scopus.com/pages/publications/85065572301

M3 - ???researchoutput.researchoutputtypes.contributiontoconference.paper???

AN - SCOPUS:85065572301

SP - 80

EP - 83

T2 - 17th Canadian Conference on Computational Geometry, CCCG 2005

Y2 - 10 August 2005 through 12 August 2005

ER -

Computing the widest empty boomerang

תקציר

כנס

קבצים וקישורים אחרים

טביעת אצבע

פורמט ציטוט ביבליוגרפי