기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
Minimizing the Average Distance of Separated Points on the Plane in the L1-Distance
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • Minimizing the Average Distance of Separated Points on the Plane in the L1-Distance
  • Minimizing the Average Distance of Separated Points on the Plane in the L1-Distance
저자명
Kim. Jae-Hoon
간행물명
Journal of information and communication convergence engineering
권/호정보
2012년|10권 1호|pp.1-4 (4 pages)
발행정보
한국정보통신학회
파일정보
정기간행물|ENG|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

Given separated points divided by a line, called a wall, in a plane, we aim to make a gate in the wall to connect the separated points to each other. In this setting, the problem is to find a location for the gate that minimizes the average distance between the points. The problem is a variant of the well-known facility location problem, which is extensively studied in the fields of operations research, location theory, theoretical computer science, and so on. In this paper, we consider the $L^1$-distance of the points in the plane. The points are projected onto the wall and so the problem is transformed to a proximity problem of points on a line. Then it is shown that the transformed problem is related to the weighted median problem of points on the line. Therefore, we obtain an O(n log n)-time algorithm to solve our problem.