Computing a planar widest empty α-siphon in o(n3) time

Boaz Ben-Moshe; Binay K. Bhattacharya; Sandip Das; Daya R. Gaur; Qiaosheng Shi

Computing a planar widest empty α-siphon in o(n³) time

Boaz Ben-Moshe, Binay K. Bhattacharya, Sandip Das, Daya R. Gaur, Qiaosheng Shi

מדעי המחשב

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

1 ציטוט ‏(Scopus)

תקציר

Given a set of n points P in the Euclidean plane, we consider the problem of locating a 1-corner polygonal chain X such that min_p∈P d(p, X) is maximized. The polygonal chain has the added property that its interior angle is α and it partitions P. In this note we present an algorithm that solves the problem in o(n³) time and space. The previous best running time for this problem was O(n³ log² n) time [2].

שפה מקורית	אנגלית
עמודים	33-36
מספר עמודים	4
סטטוס פרסום	פורסם - 2007
אירוע	19th Annual Canadian Conference on Computational Geometry, CCCG 2007 - Ottawa, ON, קנדה משך הזמן: 20 אוג׳ 2007 → 22 אוג׳ 2007

כנס

כנס	19th Annual Canadian Conference on Computational Geometry, CCCG 2007
מדינה/אזור	קנדה
עיר	Ottawa, ON
תקופה	20/08/07 → 22/08/07

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

Link to publication in Scopus

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

@conference{301ca3d9e36d4960a9b7327c6a1e4b0b,

title = "Computing a planar widest empty α-siphon in o(n3) time",

abstract = "Given a set of n points P in the Euclidean plane, we consider the problem of locating a 1-corner polygonal chain X such that minp∈P d(p, X) is maximized. The polygonal chain has the added property that its interior angle is α and it partitions P. In this note we present an algorithm that solves the problem in o(n3) time and space. The previous best running time for this problem was O(n3 log2 n) time [2].",

author = "Boaz Ben-Moshe and Bhattacharya, {Binay K.} and Sandip Das and Gaur, {Daya R.} and Qiaosheng Shi",

year = "2007",

language = "אנגלית",

pages = "33--36",

note = "19th Annual Canadian Conference on Computational Geometry, CCCG 2007 ; Conference date: 20-08-2007 Through 22-08-2007",

}

TY - CONF

T1 - Computing a planar widest empty α-siphon in o(n3) time

AU - Ben-Moshe, Boaz

AU - Bhattacharya, Binay K.

AU - Das, Sandip

AU - Gaur, Daya R.

AU - Shi, Qiaosheng

PY - 2007

Y1 - 2007

N2 - Given a set of n points P in the Euclidean plane, we consider the problem of locating a 1-corner polygonal chain X such that minp∈P d(p, X) is maximized. The polygonal chain has the added property that its interior angle is α and it partitions P. In this note we present an algorithm that solves the problem in o(n3) time and space. The previous best running time for this problem was O(n3 log2 n) time [2].

AB - Given a set of n points P in the Euclidean plane, we consider the problem of locating a 1-corner polygonal chain X such that minp∈P d(p, X) is maximized. The polygonal chain has the added property that its interior angle is α and it partitions P. In this note we present an algorithm that solves the problem in o(n3) time and space. The previous best running time for this problem was O(n3 log2 n) time [2].

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

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

AN - SCOPUS:69049088913

SP - 33

EP - 36

T2 - 19th Annual Canadian Conference on Computational Geometry, CCCG 2007

Y2 - 20 August 2007 through 22 August 2007

ER -

Computing a planar widest empty α-siphon in o(n3) time

תקציר

כנס

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

טביעת אצבע

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

Computing a planar widest empty α-siphon in o(n³) time