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

!!Conference

!!Conference	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

ملخص

!!Conference

الملفات والروابط الأخرى

بصمة

قم بذكر هذا